Algorithms · interview field notes

Merge Sorted Array: fill from the back

Two sorted arrays, merged in place into the first — which conveniently has exactly enough empty room at its tail. Merge forward and you trample unread values; merge backward and the empty space is always right where you need to write. O(m + n) time, O(1) space.

givennums1 becomesnote

[1,2,3,0,0,0] + [2,5,6][1,2,2,3,5,6]m=3, n=3

[1] + [][1]n=0, nothing to do

[0] + [1][1]m=0, take nums2

nums1 has length m + n: the first m slots are real, the last n are zero placeholders to be filled.

Why does merging left-to-right force you to use extra space?

Going right-to-left, why is the slot you write to always safe to overwrite?

The trap

Forward merging collides

The instinct is to merge left-to-right, smallest first. It reads fine until the moment you must write a small value from nums2 into a slot that still holds an unread value of nums1. Watch it break.

Why forward merging collides

nums1

wwrite▼

nums2

the last n slots of nums1 are empty (·)

The tempting approach: merge forward. Walk both arrays from the left, and write the smaller front value into the front of nums1.

01 / 04

The fix is direction

Merge backward, into the empty tail

Flip it around. Write the largest remaining value into the last slot — which is empty. Each write lands in space we no longer need to read, so there's never a collision. Step through the whole merge.

Merge backward · fill the empty tail first

nums1

p1▼

pwrite▼

nums2

p2▼

p1 = m−1 = 2 · p2 = n−1 = 2 · p = m+n−1 = 5

Three pointers, all at the end: p1 on nums1's last real value, p2 on nums2's last, and the write cursor p on the very last slot — which is empty. We fill from the right.

01 / 06

Say this

"Three pointers from the back: p1, p2, and a write cursor p. At each step I copy the larger of nums1[p1] and nums2[p2] into nums1[p] and step that pointer back. Because the tail is empty, every write is safe — and when nums2 is done, nums1's leftovers are already sorted in place."

The whole thing

Five lines, one pass

No second array, no sort — just three pointers walking backward through both inputs at once.

the whole solution · javascriptO(m + n) time · O(1) space

function merge(nums1, m, nums2, n) {

    let p1 = m - 1;            // last real value in nums1

    let p2 = n - 1;            // last value in nums2

    let p  = m + n - 1;        // last slot — starts empty

    while (p2 >= 0) {          // until nums2 is exhausted

        if (p1 >= 0 && nums1[p1] > nums2[p2])

            nums1[p--] = nums1[p1--];   // bigger came from nums1

        else

            nums1[p--] = nums2[p2--];   // bigger (or tie) from nums2

}

}

Looping on p2 >= 0 is the subtle part: when nums2 runs out, the rest of nums1 is already in place — so there's nothing left to do.

The one-liner to land

"Merge from the back. Largest of the two tails goes into the last empty slot; walk all three pointers leftward. The empty space sits exactly where I write, so it's in place and conflict-free — O(m + n) time, O(1) space."