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

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.
2. Sort nums1.

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

Time: O((m + n) log(m + n))

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

If we merge from the front, we would overwrite elements of nums1 that have not been processed yet.

The key observation is that the end of nums1 is empty. So we fill nums1 from the back, placing the largest elements first.

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

At each step, compare nums1[i] and nums2[j].

Place the larger one at nums1[k], then move that pointer and k one step left.

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

Code Solutions

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--;
        }
    }
};

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.

Why This Is Better Than Brute Force

The brute-force approach re-sorts everything, even though both arrays are already sorted.

The three-pointer approach uses that existing order. Each step places exactly one element in its final position, so every element is touched only once.

This reduces the solution from O((m + n) log(m + n)) to O(m + n) time.

Complexity

How to Explain It in an Interview