Please see github.com/anusha-murali for all of my repositories.
In this LeetCode problem (Problem #88), we use three pointers to arrive at an efficient solution.
Problem: 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 becausem = 0
, there are no elements innums1
. The0
is only there to ensure the merge result can fit innums1
.
Solution
We will use three pointers, namely firstPtr
, which points to the last element of nums1
, secondPtr
, which points to the last element of nums2
, and thirdPtr
, which points to the last *index of nums1
. Note that the length of nums1
is equal to the actual number of elements in nums1
($m$) and the number of elements in nums2
($n$).
def merge(nums1, m, nums2, n):
"""
Do not return anything, modify nums1 in-place instead.
"""
firstPtr = m - 1
secondPtr = n -1
thirdPtr = m + n - 1
while firstPtr >= 0 and secondPtr >= 0:
if nums1[firstPtr] > nums2[secondPtr]:
nums1[thirdPtr] = nums1[firstPtr]
firstPtr -= 1
else:
nums1[thirdPtr] = nums2[secondPtr]
secondPtr -= 1
thirdPtr -= 1
The code is self-explantory. If a nums1
element is greater than the nums2
element being compared, then we copy the nums1
element to the index pointed to by thirdPtr
and decrement both the firstPtr
and the thirdPtr
. Otherwise, we decrement both the secondPtr
and the thirdPtr
.
Finally, we copy any remaining nums2
elements to the remaining spaces of nums1
.
Runtime: Since the while
loop executes only $n+m$ times, the runtime is $O(n+m)$. As we are not using any additional storage, the space complexity is $O(1)$.