[LeetCode] 88. Merge Sorted Array

🧠 Remember: “Biggest first, from the back.”

The problem — 20 seconds

nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3 → [1, 2, 2, 3, 5, 6] — merged into nums1, in place.

Original on LeetCode

Both inputs are sorted. The only twist: nums1 carries its answer space as trailing zeroes. The question is where you start writing.

back-fill:  6 → w=5,  5 → w=4,  3 → w=3,  2 → w=2  ✓
front-fill: 1 vs 2 → write 1… then 2 overwrites the 2 you haven't read  ✗

Your first instinct

Concatenate and sort: O((m+n) log(m+n)). Correct, but it ignores the one fact you are given — both halves are already sorted.

Or merge from the front into nums1. That clobbers values you have not read yet, forcing quadratic shifting to dodge a problem the buffer already solves.

The turning point

The buffer sits at the back, so write at the back. Point at both tails, park the larger at w, step down. Every write lands on buffer or a merged slot — unmerged values are never touched.

Watch it work

Press Play: p1/p2 compare tails, w retreats, ties go to nums2.

Interactive visual · Back-Fill

Can you merge without clobbering?

Both arrays are sorted, but nums1's tail is empty buffer. Write the biggest remaining element at w and walk backwards — nothing unmerged ever gets overwritten.

nums1 (m = 3 + buffer) writes go to w

nums2 (n = 3)

result

Step 1 / 1 Speed

1p1=m-1, p2=n-1, w=m+n-1

2while p1>=0 and p2>=0:

3write larger at w; move pointer; w-=1

4copy leftover nums2

Quick check — make it stick

Why fill from the back?

🧠 Memory hook: “Biggest first, from the back.” The tail is free space — park the largest leftover there and nothing gets clobbered.

What the code is really saying

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1, p2, w = m - 1, n - 1, m + n - 1
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[w] = nums1[p1]
                p1 -= 1
            else:
                nums1[w] = nums2[p2]
                p2 -= 1
            w -= 1
        if p2 >= 0:
            nums1[: p2 + 1] = nums2[: p2 + 1]

Read it as the visual: compare tails, write the winner at w, retreat. The last line copies leftover nums2 entries — leftover nums1 entries are already home.

Why it works

Invariant: everything right of w is merged and final. Each step shrinks the unmerged region by one, so the loop ends with w filled.

Time O(m+n), space O(1).

🧠 Remember

Merge → “Biggest first, from the back.” Free space at the tail means the write pointer can never lap the read pointers.

🔁 Try this: what if the extra space were at the front instead? (Hint: mirror everything — merge from the front, smallest first.)

Related: Two Sum · 3Sum · Sort Array By Parity