Two Pointers · LC #88

Merge Sorted Array

Merge two sorted arrays in-place by filling from the back, avoiding the overwrite problem that plagues forward-fill approaches. Classic O(m+n) time, O(1) space.

easyLC #88AMZ★★GOO★★META★★★MSFT★★AAPL★★

Mark as done

Confidence

Ask GPT Practice on LeetCodePractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

You have two sorted arrays `nums1` (length `m+n`, first `m` elements are valid) and `nums2` (length `n`). Merge `nums2` into `nums1` in-place, sorted.

Sample I/O

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

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

Time: O(m+n) · Space: O(1)

Intuition

How to Think About It

Intuition

If you merge forward you risk overwriting nums1 elements you haven't read yet. The key insight: fill from the BACK - the tail of nums1 is empty padding, so writing there is safe. Compare the largest-remaining from each array and place the winner at the current tail.

Core Concept

Three pointers: `p1 = m-1` (last valid in nums1), `p2 = n-1` (last in nums2), `p = m+n-1` (write position). While both p1 and p2 ≥ 0: place max(nums1[p1], nums2[p2]) at nums1[p], decrement corresponding pointer and p. After the loop, if p2 ≥ 0, copy remaining nums2 elements (p1 remainder is already in place).

When to use

In-place merge of two sorted sequences; the merge step of bottom-up merge sort; any problem where one array has a "tail buffer".

When NOT to use

When merging into a new array is acceptable - forward two-pointer is simpler. When more than two arrays are involved (use a min-heap).

Key Insights

What to Know Cold

Writing from the back eliminates any risk of overwriting unread elements.
The remaining-nums2 copy loop is essential - remaining nums1 elements are already in their correct positions.
If m=0 you just copy all of nums2; the main loop never executes.
Variation: if nums1 can be resized, append nums2 then sort - but that is O((m+n) log(m+n)), not O(m+n).
This backward-fill trick generalises: "Fill from the end whenever the destination overlaps with the source."

1 example

Worked Examples

Backward Three-Pointer Merge

nums1=[1,2,3,0,0,0] m=3, nums2=[2,5,6] n=3. Fill the tail of nums1 without extra space.

p1=2, p2=2, p=5. Compare 3 vs 6 → place 6 at index 5. p2=1, p=4. Compare 3 vs 5 → place 5. Continue until p2 exhausted.

def merge(nums1, m, nums2, n):
    p1, p2, p = m - 1, n - 1, m + n - 1
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]; p1 -= 1
        else:
            nums1[p] = nums2[p2]; p2 -= 1
        p -= 1
    while p2 >= 0:
        nums1[p] = nums2[p2]; p -= 1; p2 -= 1

Demonstrates backward-fill - the O(1)-space in-place merge trick that underlies merge sort and appears in META and AAPL phone screens.