Merge Sorted Array

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 because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

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)$.

Back to Two Pointers Problems

---

anusha-murali.github.io