[LeetCode 88] Merge Sorted Array

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
• -109 <= nums1[i], nums2[j] <= 109

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

Answer

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.
        """
        midx = m - 1
        nidx = n - 1
        right = m + n - 1

        while nidx >= 0:
            if midx >= 0 and nums1[midx] > nums2[nidx]:
                nums1[right] = nums1[midx]
                midx -= 1
            else:
                nums1[right] = nums2[nidx]
                nidx -= 1
            
            right -= 1

Solution

The first important thing to understand is that nums1 is being modified in-place inside the function. When you use nums1[:] or directly assign values to nums1[idx], the changes will be reflected outside the function as well.

The second key point is that we want to avoid using sort() and instead solve the problem with O(m + n) time complexity. This can be a bit tricky.

To do this, we first define indices midx for nums1 and nidx for nums2. According to the constraints, the total length of nums1 is m + n. So, we can come up with the following strategy:

If we start filling values from the beginning, smaller values in nums1 might get overwritten before being compared or moved. Therefore, it is better to fill from the end, comparing the values from both arrays and placing the largest one at the rightmost available position in nums1.

This approach ensures that values in nums1 that are greater than those in nums2 are already positioned correctly within the [m, m + n) range, and inserting smaller values from nums2 into the [0, m) range won’t cause any issues.

Let’s walk through an example:

Approach

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

◽️ Question:
How should we iterate through the input arrays?

My answer is: from the end. Why?

Because in nums1, we have values at index 0, 1, and 2. The smallest is 1, then 2. The next smallest value, 2, is in nums2.
If we try to insert it at the front, like this:

[1,2,2,0,0,0]
Then we lose the original 3, which we might still need. Keeping that value temporarily is a bit messy, right?

But if we start from the end, we have empty spots at index 3, 4, and 5 in nums1. We can just place the larger values there, and no original data is lost.

Since both arrays are sorted in non-decreasing order, all we need to do is compare the last elements and insert the larger one at the current rightmost index.

Let’s see this in action:

           ↓     r
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3　　　　　　　　　　　
           ↑

r is the index where the next largest number will be placed.
First, compare 3 and 6. Since 6 > 3, we place 6 at index r and move both r and the nums2 pointer backward:

       ↓   r
[1,2,3,0,0,6]
[2,5,6]
   ↑

Next, compare 3 with 5:

     ↓ r
[1,2,3,0,5,6]
[2,5,6]
   ↑

Then compare 3 with 2:

   ↓ r
[1,2,3,3,5,6]
[2,5,6]
 ↑

Now compare 2 with 2. Let’s insert the one from nums2:

 ↓ r
[1,2,2,3,5,6]
[2,5,6]
↑

Now the pointer for nums2 has reached -1, so the iteration ends.
The final result is [1,2,2,3,5,6].