p04 — Merge Sorted Array

Source: LeetCode 88 · Easy · Topics: Array, Two Pointers, Sorting Companies: Facebook (high), Bloomberg (high), Microsoft (high), Adobe (medium), Apple (medium) Loop position: phone screen or onsite warmup; often paired with a follow-up to merge k arrays (LC 23 — Merge k Sorted Lists)

1. Quick Context

A deceptively simple problem with a sharp trick: you must merge in place in nums1 (which has extra trailing zeros). The naive approach (merge from the left) requires shifting → O(N²). The optimal approach (merge from the right, writing the largest elements into the back) is O(M+N), O(1) extra.

What it tests: in-place pointer manipulation and the recognition that writing backwards avoids the overwrite problem. The trap: candidates instinctively merge from the front and either get O(N²) or need an extra buffer (O(N) space) and forget that the prompt forbids it.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/merge-sorted-array/

12-min timer. Cold attempt. The “merge from the back” insight should be the first thing you reach for — if not, that’s a strong signal you need this rep.

3. Prerequisite Concepts

• Two-pointer technique — phase-02 §1
• “In-place transformation” pattern — when extra buffer is forbidden

4. How to Approach

Restate: nums1 has length m + n. Its first m entries are valid, sorted; the last n are placeholder zeros. nums2 has n valid sorted entries. Merge so that nums1 holds all m + n values sorted. Modify nums1 in place.

Clarify:

• “Can I use O(N) extra space?” (Usually no — the whole point is in-place. ASK.)
• “Are duplicates allowed?” (Yes; merge is stable.)
• “Can m or n be 0?” (Yes. Both edge cases.)
• “Are negative numbers allowed?” (Yes, per constraints.)

Examples:

• nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3 → [1,2,2,3,5,6]
• nums1=[1], m=1, nums2=[], n=0 → [1] (n=0 edge)
• nums1=[0], m=0, nums2=[1], n=1 → [1] (m=0 edge)
• nums1=[4,5,6,0,0,0], m=3, nums2=[1,2,3], n=3 → [1,2,3,4,5,6] (all of nums2 < all of nums1 — tests handling when nums2 isn’t exhausted)

Brute force: Copy nums2 into the tail of nums1, then sort. O((M+N) log (M+N)). Trivially correct but wastes the “already sorted” property.

Pattern: Two sorted sequences + in-place + extra room at the END → merge from the back, largest first.

Optimal:

i = m - 1            # pointer into nums1's valid part
j = n - 1            # pointer into nums2
write = m + n - 1    # pointer into nums1's tail (where to write next)
while j >= 0:        # only need to keep going while nums2 has elements
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[write] = nums1[i]
        i -= 1
    else:
        nums1[write] = nums2[j]
        j -= 1
    write -= 1

Why we loop on j >= 0, not i >= 0: If nums2 is exhausted, the remaining nums1[0..i] is already in its final position (since we wrote bigger elements to the right). If nums1’s valid prefix is exhausted (i < 0), we must still copy remaining nums2 elements. The loop condition reflects which case requires action.

Correctness: At each step we write the larger of the two unprocessed maxima into the next free slot from the right. The slot is always at or past the “write frontier”, which is at index i + j + 1. Since write = i + j + 1 decreases monotonically and i + j is the count of unprocessed elements minus 2, the slot is never one we still need to read from. No overwrite.

5. Progressive Hints

hints.md. One at a time.

6. Deeper Insight — Why It Works

The reverse-merge insight: Merging from the front into nums1 would overwrite valid nums1 data before reading it (because the write pointer would catch up to the read pointer for nums1). Merging from the back writes into slots that are guaranteed unused (either they’re trailing zeros, or they’re slots holding values already moved).

The invariant: At any point, nums1[write+1 .. m+n-1] contains the largest (m+n-1 - write) elements of the final merged result, in sorted order. nums1[0..i] and nums2[0..j] are the unprocessed prefixes.

Why i+j+1 == write always: Initially i+j+1 = (m-1) + (n-1) + 1 = m+n-1 = write. Each iteration decrements write by 1 and decrements either i or j by 1, so the relation holds. Therefore write is always one past i+j, the position right after the unprocessed prefixes — guaranteed empty. This is the formal proof of “no overwrite.”

7. Anti-Pattern Analysis

Wrong #1 — Front merge with shift:

i, j = 0, 0
while j < n:
    if i < m and nums1[i] <= nums2[j]:
        i += 1
    else:
        # shift nums1[i..m-1] right to make room
        nums1.insert(i, nums2[j])  # O(M) shift!
        nums1.pop()                # O(M)
        i += 1
        m += 1
        j += 1

Correct but O((M+N) × M) — quadratic. Senior interviewers see this and ask “can you do better?” — if you can’t pivot to the reverse-merge, you’ve revealed a gap.

Wrong #2 — Copy nums1 valid prefix to an aux buffer:

aux = nums1[:m]
# then merge aux and nums2 into nums1 from the front

Correct and O(M+N) time but O(M) extra space. Violates the in-place spirit — passes LC but loses interview points.

Wrong #3 — Sort after concat:

nums1[m:] = nums2
nums1.sort()

O((M+N) log (M+N)). Passes LC. But: “you ignored the ‘sorted input’ property — what was the point of this problem?”

Wrong #4 — Forget the i >= 0 guard in the comparison:

while j >= 0:
    if nums1[i] > nums2[j]:   # IndexError when i goes negative

The guard if i >= 0 and nums1[i] > nums2[j] matters when nums1’s valid prefix is exhausted before nums2.

8. Skills & Takeaways

Pattern: write-backwards-to-avoid-overwrite. Direct applications:

• LC 26 / 27 / 80 — Remove Duplicates / Remove Element (write-forward variant)
• LC 283 — Move Zeroes
• LC 977 — Squares of a Sorted Array (write from back: largest absolute value at each end)
• LC 167 — Two Sum II (two-pointer from both ends; sibling family)

The “merge from back” trick generalizes: Any in-place merge where one container has trailing room becomes O(N) by writing backward. Used in some qsort partition tricks and in compaction passes of generational garbage collectors.

9. When to Move On

• Solved unaided <10 min using reverse-merge
• Tested m=0, n=0, all-of-nums2-smaller, equal elements
• Articulated why front-merge fails (overwrite) and back-merge succeeds (slot guaranteed free)
• Stress test passes
• Solved LC 977; saw the same write-backwards idea

10. Company Context

Facebook / Meta

• Frame: Often appears as a warmup before LC 23 (Merge k Sorted Lists). The interviewer expects you to do p04 in 5 min, then they ask “now generalize to k arrays.”
• What they want: Reverse-merge offered without prompting. The phrase “I’ll merge from the back to avoid shifting” is a green check.
• Trap: They give you nums1 with extra space already allocated. Candidates who treat nums1 as size-m and try to grow it don’t see the “trailing zeros” hint.

Bloomberg

• Frame: Often as merge of two sorted price-tick streams (“merge into a single time-ordered view”).
• Extension: “Now they may have duplicate timestamps — preserve order from stream A first.” Tests stable-merge awareness.

Microsoft

• Frame: Phone screen warmup. They watch your pointer manipulation cleanliness.
• What they want: Correct, no off-by-one, comment on the loop condition. Boring + correct = pass.

Adobe

• Frame: Often given with the explicit constraint “no extra memory”. Tests whether you internalize the in-place requirement.

11. Interviewer’s Lens

12. Level Delta

13. Follow-up Questions & Full Answers

Q1: “Now merge k sorted arrays into one.” → LC 23 family

Answer: Min-heap of (value, array_id, element_id). Pop smallest, append to output, push the next from the same array. O(N log k) where N is total elements. For very large k, consider tournament tree (same complexity, lower constant).

Q2: “What if nums1 doesn’t have extra room at the end — same length as valid data?”

Answer: No way to merge in place in O(M+N). You’d need O(min(M,N)) extra space minimum (proof: there must be storage for the merge frontier). Standard out-of-place merge.

Q3: “What if both arrays are huge and stored on disk?”

Answer: External merge sort’s merge phase. Read both arrays in buffered chunks; merge into output buffer; flush when full. Classical pattern. The key complexity unit becomes I/O, not comparisons.

Q4: “Merge two sorted linked lists in place.” → LC 21

Answer: Two-pointer with rewiring. Maintain a dummy head + a tail pointer. At each step, point tail.next to the smaller of a.val, b.val, advance that pointer. After the loop, append whatever remains. O(M+N), O(1) extra.

Q5: “How do you test?”

Answer: (1) Edge: m=0, n=0, all-A-smaller, all-A-larger, equal elements, single-element each. (2) Property: brute (sort after concat) vs optimal on random sorted inputs, must agree element-for-element. (3) Adversarial: very different sizes (m=1, n=10⁵) — confirms loop conditions handle imbalance.

14. Full Solution Walkthrough

See solution.py.

• merge_brute(nums1, m, nums2, n): append nums2 then sort. Oracle.
• merge(nums1, m, nums2, n): reverse-merge with three pointers. Mutates nums1 in place.
• stress_test: random sorted arrays of random sizes; brute vs optimal must produce identical nums1.

15. Beyond the Problem

Real systems this is the kernel of:

• Database compaction: LSM trees (LevelDB, RocksDB, Cassandra) periodically merge sorted SSTables. The merge phase is exactly this algorithm, scaled to disk-resident sorted runs with buffered I/O.
• Log merging: distributed tracing systems (Jaeger, Zipkin) merge per-shard time-sorted spans into a global view.
• External sort: when data exceeds RAM, sort runs in memory, write to disk, then merge runs — same algorithm.
• Generational garbage collectors: compaction passes merge live objects into a destination region; the “write backwards” idea appears in some collectors to avoid overwriting unmoved objects.

Principal-engineer code review: “If this is being called in a tight loop, the algorithm is fine but the API is wasteful — caller must allocate nums1 with extra capacity. Consider a builder pattern that allocates the output buffer once and reuses it, especially if M and N vary. Also: the function silently assumes nums1 has length m+n; add a precondition or a contract test, or someone will pass an under-sized array and you’ll get a confusing IndexError instead of a clear contract violation.”