Leetcode 88. Merge Sorted Array
Explanation for Leetcode 88 - Merge Sorted Array, and its solution in Python.
Problem
Leetcode 88 - Merge Sorted Array
Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.
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].
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.
Approach
We’re trying to merge two arrays and place them in nums1. We can sort the array by having 3 pointers on each left = nums1(where nums1 actually ends), i = end of nums1, right = end of nums2.
We can then run a while loop to compare nums1[left] and nums2[right] then if nums1[left] is bigger we can decrement left pointer else we can decrement right pointer. Then we place the bigger number in nums1[i].
After the first while loop is done, we can put the remainder in nums1 array
Visualization of the Approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
nums1 = [1,2,3,0,0,0], nums2 = [2,5,6]
l i r
Since nums1[l] <= nums2[r]: place nums2[r] in nums1[i] and decrement r and i
nums1 = [1,2,3,0,0,6], nums2 = [2,5,6]
l i r
Since nums1[l] <= nums2[r]: place nums2[r] in nums1[i] and decrement r and i
nums1 = [1,2,3,0,5,6], nums2 = [2,5,6]
l i r
Since nums1[l] > nums2[r]: place nums2[r] in nums1[i] and decrement r and i
nums1 = [1,2,3,3,5,6], nums2 = [2,5,6]
l i r
Since nums1[l] <= nums2[r]: place nums2[r] in nums1[i] and decrement r and i
nums1 = [1,2,2,3,5,6], nums2 = [2,5,6]
l
i
Since r < 0, we can stop while loop and run a loop on remainder arrays
Thus, nums1 = [1,2,2,3,5,6]
Here is the Python code for the solution:
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
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.
"""
# initializing the index of left, right, i
left = m-1
right = n-1
i = len(nums1)-1
# while left and right isn't iterated
while left >= 0 and right >= 0:
if nums1[left] > nums2[right]:
nums1[i] = nums1[left]
left -= 1
else:
nums1[i] = nums2[right]
right -= 1
i -= 1
# we don't need to worry about left, because if left >= 0, the remainder should be already in nums1
# while right isn't iterated
while right >= 0:
nums1[i] = nums2[right]
right -= 1
i -= 1
Time Complexity and Space Complexity
Time Complexity: $O(n + m)$ where $m$ is length of nums1 $n$ is length of nums2
Space Complexity: $O(1)$