Merge Sorted Array — Backwards Two-Pointer for In-Place Merging

Problem Statement#

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 each. Merge nums2 into nums1 as one sorted array. nums1 has length m plus n with the last n positions reserved for nums2.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

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

Input:  nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Why This Problem Matters#

Merge Sorted Array is the cleanest two-pointer array interview question that tests reverse iteration. Meta and Microsoft love it because the obvious forward merge fails — you would overwrite unread elements in nums1. The elegant solution walks both pointers from the back and writes from the back.

This pattern is the foundation of merge sort, the merge step in external sorting, and any in-place stream join. Knowing the backwards merge signals comfort with non-obvious pointer arithmetic and is a string FAANG favorite for systems candidates.

The Core Insight#

Forward merging requires extra space because writing to nums1[0] would clobber nums1[0] before we read it. Walking from the back, the write index starts at m plus n minus 1, where there is guaranteed empty space.

We compare nums1[i] and nums2[j] and place the larger one at the write index, then decrement the appropriate pointer. When nums2 runs out we are done because remaining nums1 elements are already in place.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def merge(self, nums1, m, nums2, n):
        i, j, k = m - 1, n - 1, m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

var merge = function(nums1, m, nums2, n) {
    let i = m - 1, j = n - 1, k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
};

Time: O(m + n) — every element is written once. Space: O(1) — in-place merge.

Common Mistakes#

• Walking forward and overwriting unread nums1 elements.
• Forgetting to handle remaining nums2 elements when nums1 runs out.
• Comparing using greater than or equal, which is fine but make the choice consciously.
• Returning the array — the function mutates nums1 in place.

Interview Tips#

• State why forward merge fails before introducing reverse merge.
• Confirm the m plus n length contract on nums1.
• Note that remaining nums1 elements need no copy because they are already in place.
• Walk through pointers on a small example before coding.

Follow-up Questions#

• Merge k sorted arrays? Hint: min-heap.
• Merge sorted linked lists? Hint: pointer manipulation, no extra array.
• What if nums1 had no buffer? Hint: copy nums1 then merge forward.
• What about merging in descending order? Hint: walk from front.
• Stream version? Hint: heap-based merge from k iterators.

Key Takeaways#

• LeetCode 88 is solved by walking pointers from the back.
• Time O(m + n), space O(1) — the FAANG bar for in-place merge.
• Forward merge fails because of overwrites; reverse merge avoids them.
• Remaining nums1 elements need no copy if nums2 finishes first.
• Foundation pattern for merge sort and external sort.
• Confirm in-place mutation with the interviewer.
• Common Meta and Microsoft two-pointer warmup question.