88. Merge Sorted Array

Merge sorted nums2 into sorted nums1 in place. The trick: fill from the backwith three pointers, so you never overwrite a value you haven't read yet.

● EasyTwo PointersIn-place MergeTypeScript

PROBLEM What we're solving

Two sorted arrays, merged into one sorted array — but written back into nums1, which already has n empty slots at the end. nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 → [1,2,2,3,5,6]. No new array allowed; do it in place.

KEY IDEA Fill from the back

Insight → the empty room is at the end of nums1, and the largest merged value belongs at the end. So write back-to-front: compare the two current largest values and drop the bigger one into the rightmost open slot. Because that slot is always at or beyond every value you still need to read, you never clobber unread data.

RECIPE Three pointers, walking left

0 · Anchor three pointers. i = m - 1 (last real value in nums1), j = n - 1 (last in nums2), k = m + n - 1 (last slot — where we write).
1 · Compare and place the bigger. While j >= 0: if nums1[i] > nums2[j], write nums1[i] and i--; otherwise write nums2[j] and j--. Either way k--.
2 · Stop when j runs out. Loop on j, not i: any leftover nums1 values are already sitting in their final sorted positions — nothing to move.
3 · Guard i >= 0. If nums1 is exhausted first, fall through to copying the rest of nums2.

Classic confusion → people instinctively merge front-to-back like the classic two-array merge. But the open slots are at the back, so a forward write would overwrite nums1 values you still need to read. Going backward sidesteps the whole problem — no temp array required.

COST Complexity & alternatives

Concat then sort

O((m+n) log(m+n))

One line, but throws away the "already sorted" gift.

Back-to-front merge

O(m + n)

Each value touched once; O(1) extra space.

Space note

A forward merge into a fresh array is also O(m + n) time but needs O(m + n) extra space (or careful shifting). The back-to-front trick is what buys you O(1) extra space while staying linear.

Pattern transfer → writing from the back to merge in place reappears in Merge k Sorted Lists (heap of heads), the merge step of merge sort, and any "combine sorted runs without extra room" task. The general lesson: when the free space is at one end, fill toward it.

RUN IT Merge from the back, biggest first

nums1 =m =nums2 =n =

step 0 / 13

STARTStart from the back: i = 2 (last real value in nums1), j = 2 (last in nums2), k = 5 (last slot to write).

1function merge(nums1: number[], m: number, nums2: number[], n: number): void {
2▶  let i = m - 1;          // last real value in nums1
3▶  let j = n - 1;          // last value in nums2
4▶  let k = m + n - 1;      // last slot overall (write here)
5 
6  while (j >= 0) {        // while nums2 still has values to place
7    if (i >= 0 && nums1[i] > nums2[j]) {
8      nums1[k] = nums1[i]; // nums1's value is bigger → take it
9      i--;
10    } else {
11      nums1[k] = nums2[j]; // nums2's value wins (or nums1 exhausted)
12      j--;
13    }
14    k--;                   // move the write pointer left
15  }
16}

nums1102132030405

State

nums1[i]

nums2[j]

write slot knums1 pointer inums2 pointer jfinalized

slowfast

TYPESCRIPT The solution, annotated

merge.ts
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let i = m - 1;          // last real value in nums1
  let j = n - 1;          // last value in nums2
  let k = m + n - 1;      // last slot overall (write here)

  while (j >= 0) {        // while nums2 still has values to place
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[k] = nums1[i]; // nums1's value is bigger → take it
      i--;
    } else {
      nums1[k] = nums2[j]; // nums2's value wins (or nums1 exhausted)
      j--;
    }
    k--;                   // move the write pointer left
  }
}

Reading it block by block

Lines 2–4 — anchor at the back. i points at the last real value of nums1, j at the last of nums2, and k at the very last slot (m + n - 1) where the next merged value will be written.

Line 6 — loop on j. We only need to keep going while nums2 still has values to place. When j hits -1, every remaining nums1 value is already in its correct spot.

Lines 7–9 — nums1's value wins. The i >= 0 guard prevents reading past the front of nums1. If nums1[i] > nums2[j], copy it down to nums1[k] and step i left.

Lines 11–13 — nums2's value wins. Otherwise (including when nums1 is exhausted, i < 0) drop nums2[j] into nums1[k] and step j left.

Line 15 — slide the writer. After every placement, k-- moves the write head one slot left. The loop exits with nums1 fully merged and no extra array allocated.

Complexity → O(m + n) time — each value is written exactly once. O(1) extra space — the merge happens inside nums1 with three index pointers.

INTERVIEWFollow-ups they'll ask

"Why merge from the back?" The empty slots are at the end; writing forward would overwrite nums1 values you still need to read.
"Why loop on j and not i?" Leftover nums1 values are already in place; only unplaced nums2 values force more work.
"What if nums1 empties first?" The i >= 0 guard sends control to the else branch, copying the rest of nums2 straight down.
"Generalize to k sorted arrays?" Use a min-heap of the current heads (Merge k Sorted Lists), which is O(N log k).

OPTIMAL Two Pointers

merge.ts
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let i = m - 1;          // last real value in nums1
  let j = n - 1;          // last value in nums2
  let k = m + n - 1;      // last slot overall (write here)

  while (j >= 0) {        // while nums2 still has values to place
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[k] = nums1[i]; // nums1's value is bigger → take it
      i--;
    } else {
      nums1[k] = nums2[j]; // nums2's value wins (or nums1 exhausted)
      j--;
    }
    k--;                   // move the write pointer left
  }
}

Complexity → O(m + n) time — each value is written exactly once. O(1) extra space — the merge happens inside nums1 with three index pointers.

ALT 1 Concatenate then sort

O((m+n) log(m+n)) time · O(1) extra (in-place sort)

Copy nums2 over the trailing zeros, then sort the whole thing — the shortest correct answer, useful to state before optimizing.

approach-2.ts
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  for (let k = 0; k < n; k++) {
    nums1[m + k] = nums2[k];
  }
  nums1.sort((a, b) => a - b);
}

Note → Correct and tiny, but it discards the fact that both inputs are already sorted, paying an O((m+n) log(m+n)) sort instead of a linear merge. The three-pointer back-merge is O(m + n).

ALT 2 Forward merge into a temp array

O(m + n) time · O(m + n) space

The classic two-array merge: walk both forward, take the smaller, then copy back. Easy to reason about, but needs a scratch array.

approach-3.ts
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  const merged: number[] = [];
  let i = 0, j = 0;
  while (i < m && j < n) {
    merged.push(nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++]);
  }
  while (i < m) merged.push(nums1[i++]);
  while (j < n) merged.push(nums2[j++]);
  for (let k = 0; k < m + n; k++) nums1[k] = merged[k];
}

Note → Linear time, but the scratch merged array costs O(m + n) space. Merging from the back inside nums1 avoids the allocation entirely.

MNEMONIC The one-liner

"Biggest first, from the back — write where nothing important lives yet."

TRIGGERS When you see _ → reach for _

merge two SORTED arrays	two pointers, take the smaller/larger
in place, extra space at the end	fill from the back (k = m+n-1)
risk of overwriting unread data	walk pointers toward the free end
combine many sorted runs	min-heap of heads (k-way merge)

SKELETON The reusable shape

skeleton.ts
let i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
  if (i >= 0 && nums1[i] > nums2[j]) {
    nums1[k--] = nums1[i--];
  } else {
    nums1[k--] = nums2[j--];
  }
}

FLASHCARDS Tap to flip

Where do the three pointers start?

i = m - 1, j = n - 1, k = m + n - 1 — all at the back.

tap to flip

1 / 6

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

Why fill nums1 from the back rather than the front?

QUESTION 02

What are the initial values of i, j, k?

QUESTION 03

What is the loop condition?

QUESTION 04

Why is the i >= 0 check needed inside the comparison?

QUESTION 05

Time and space complexity of the back-to-front merge?

QUESTION 06

For nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3, what is the FIRST value written and to which index?

QUESTION 07

If you accidentally looped "while (i >= 0)" instead of "while (j >= 0)", what breaks?

QUESTION 08

#88 · Merge Sorted ArrayMerge nums2 into nums1 in place by writing from the BACK with three pointers, so the largest remaining value lands in the last open slot and you never overwrite an unread element. O(m+n) time, O(1) space.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Fill from the back

RECIPE Three pointers, walking left

COST Complexity & alternatives

Space note

RUN IT Merge from the back, biggest first

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Two Pointers

ALT 1 Concatenate then sort

ALT 2 Forward merge into a temp array

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _