p04 Merge Sorted Array — Progressive Hints

One hint. 5-min timer. Retry. Repeat.

Hint 1 — Why front-merge fails

If you merge from the front (smallest first) and write into nums1[0], you overwrite valid nums1[0] data before reading it. To avoid this, you’d need to shift nums1’s data right — that’s O(M) per insert, total O(M·N).

What part of nums1 is guaranteed safe to write into without overwriting valid data?

Hint 2 — The free space

The trailing zeros in nums1 are a hint. Those positions are reserved for the merge output. If you write the largest unprocessed element into the rightmost free slot, you’re writing into space that’s guaranteed not to contain valid data.

Hint 3 — Three pointers

Use:

  • i = m - 1 — pointer into the valid part of nums1 (largest unprocessed value)
  • j = n - 1 — pointer into nums2
  • write = m + n - 1 — where the next-largest goes

At each step: compare nums1[i] and nums2[j]. The larger one goes to nums1[write]. Decrement the source pointer and write.

Hint 4 — Pseudocode

i = m - 1
j = n - 1
write = m + n - 1
while j >= 0:
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[write] = nums1[i]
        i -= 1
    else:
        nums1[write] = nums2[j]
        j -= 1
    write -= 1

Two non-obvious choices:

  • Loop condition is j >= 0, not i >= 0. Why?
  • The comparison guards i >= 0 explicitly. Why?

Hint 5 — Full reasoning

Why loop on j >= 0 (not i >= 0)? When nums2 runs out, the remaining nums1[0..i] is already where it needs to be — sorted, and to the left of all written slots. No work needed. But if nums1’s valid prefix runs out first (i < 0), we must keep copying from nums2. So j >= 0 is the condition that captures “still work to do.”

Why the i >= 0 guard in the comparison? Once i < 0, accessing nums1[i] is reading from index -1 — in Python that wraps to the last element (a written slot), corrupting comparisons. The i >= 0 and ... short-circuits to the else branch (copy from nums2), correctly handling the case.

The invariant that makes it work: At every step, write == i + j + 1. That means nums1[write] is the position immediately AFTER the unprocessed prefixes — guaranteed empty/safe to overwrite. This invariant is the formal proof of “no overwrite.”

Time O(M+N), Space O(1).