leetcode-challenges/0088_merge_sorted_list_array.py at master · vdumchiviy/leetcode-challenges · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
'''
88. Merge Sorted Array
Easy

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order,
and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored
inside the array nums1. To accommodate this, nums1 has a length of m + n,
where the first m elements denote the elements that should be merged,
and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1.
The 0 is only there to ensure the merge result can fit in nums1.


Constraints:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10**9 <= nums1[i], nums2[j] <= 10**9


Follow up: Can you come up with an algorithm that runs in O(m + n) time?
'''

from typing import List


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if m == 0:
            nums1[:] = nums2
            return
        if n == 0:
            return

        pos1 = 0
        pos2 = 0
        # check the highest position in the lists
        while pos1 < m + n or pos2 < n:

            if pos1 < m + pos2 and pos2 < n:
                # inside nums1 and we have numbers in nums2

                if nums2[pos2] < nums1[pos1]:
                    # the nums2 has smaller value: insert and change pos2
                    nums1.insert(pos1, nums2[pos2])
                    pos2 = min(pos2 + 1, n)
                else:
                    # the nums1 has bigger or equal value than nums2: change pos1
                    pos1 = min(pos1 + 1, m + pos2)
            else:
                # we finished nums1, the rest values only in nums2
                while pos2 < n:
                    nums1[pos1] = nums2[pos2]
                    pos1 += 1
                    pos2 += 1
                break
        del nums1[n+m:]


sol = Solution()


nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
expected = [1, 2, 2, 3, 5, 6]
sol.merge(nums1, m, nums2, n)
print(f'nums1={nums1}, expected={expected}')
assert nums1 == expected

nums1 = [1]
m = 1
nums2 = []
n = 0
expected = [1]
sol.merge(nums1, m, nums2, n)
print(f'nums1={nums1}, expected={expected}')
assert nums1 == expected

nums1 = []
m = 0
nums2 = [1]
n = 1
expected = [1]
sol.merge(nums1, m, nums2, n)
print(f'nums1={nums1}, expected={expected}')
assert nums1 == expected

nums1 = [1, 3, 8, 0, 0, 0]
m = 3
nums2 = [5, 6, 9]
n = 3
expected = [1, 3, 5, 6, 8, 9]
sol.merge(nums1, m, nums2, n)
print(f'nums1={nums1}, expected={expected}')
assert nums1 == expected


nums1 = [-11, -9, -8, 0, 0, 0]
m = 3
nums2 = [-55, -45, -9]
n = 3
expected = [-55, -45, -11, -9, -9, -8]
sol.merge(nums1, m, nums2, n)
print(f'nums1={nums1}, expected={expected}')
assert nums1 == expected