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 nums2 into nums1 so that nums1 becomes a single array sorted in non-decreasing order.

The result must be stored inside nums1, and the function returns nothing. To make room, nums1 has a length of m + n. The first m elements are the real values, and the last n elements are 0 and should be ignored.

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?

Brute Force

A straightforward approach is to ignore the fact that both arrays are already sorted.

1. Copy every element of nums2 into the empty slots at the end of nums1, starting at index m.
2. Sort nums1.

This works, but sorting does not take advantage of the existing order of the two arrays.

class Solution {
    public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int j = 0; j < n; j++) {
            nums1[m + j] = nums2[j];
        }

        sort(nums1.begin(), nums1.end());
    }
};

• Time: O((m + n) log(m + n)). Sorting is the slow part.
• Space: O(log(m + n)) for the sorting algorithm's stack (or O(m + n) if you merge using a separate helper array).

We can improve this by merging the arrays directly, without sorting and without extra memory.

Optimal Approach: Three Pointers From the End

The natural idea is to merge from the front, like merging two sorted lists. But that overwrites elements of nums1 that have not been processed yet.

Small example first. Take nums1 = [4,5,6,0,0,0] and nums2 = [1,2,3]. The smallest value is 1, so it must go at index 0. But index 0 already holds 4, which we still need. Merging from the front destroys it.

The key observation is that the end of nums1 is empty. So we fill nums1 from the back, placing the largest elements first. Those slots are free, so nothing is overwritten.

Use three pointers:

• i at the last real element of nums1 (index m - 1).
• j at the last element of nums2 (index n - 1).
• k at the last position of nums1 (index m + n - 1). This is where we write.

At each step:

1. Compare nums1[i] and nums2[j].
2. Place the larger one at nums1[k].
3. Move the pointer we took from, and k, one step left.
4. If i has run out (i < 0), take from nums2.

When nums2 is fully placed, we are done. Any remaining elements in nums1 are already in the correct position.

class Solution {
    public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }

            k--;
        }
    }
};

Dry Run

Take nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3.

1Start: i = 2, j = 2, k = 5
2 
3Step | nums1[i] | nums2[j] | Larger      | Write at k    | i | j  | k | nums1 after
4-----|----------|----------|-------------|---------------|---|----|---|------------------
5  1  |  3       |  6       | 6 (nums2)   | nums1[5] = 6  | 2 |  1 | 4 | [1,2,3,0,0,6]
6  2  |  3       |  5       | 5 (nums2)   | nums1[4] = 5  | 2 |  0 | 3 | [1,2,3,0,5,6]
7  3  |  3       |  2       | 3 (nums1)   | nums1[3] = 3  | 1 |  0 | 2 | [1,2,3,3,5,6]
8  4  |  2       |  2       | 2 (nums2)   | nums1[2] = 2  | 1 | -1 | 1 | [1,2,2,3,5,6]
9 
10j = -1, so the loop stops.
11The remaining nums1 elements [1,2] are already in place.
12 
13Return: nums1 = [1,2,2,3,5,6]

In step 4 the two values are equal (2 and 2), so the > check is false and we take from nums2. Taking either one gives the same result.

Why Do We Loop Only While j >= 0?

There are two ways the loop can finish.

If nums2 runs out first, the remaining elements of nums1 are already sorted and already in their final positions. Nothing needs to move.

If nums1 runs out first (i < 0), the condition i >= 0 && ... fails, so the remaining nums2 elements are copied into the front of nums1.

So the only thing that must be finished is nums2.

Complexity

How to Explain It in an Interview