88. Merge Sorted Array

Quick Identifier

• Topic: arrays-hashing
• Pattern: Two Pointers (Backward Sweep)
• Hint: If you merge from the front, you will overwrite the elements of nums1 before you evaluate them. Merge from the back, placing the largest elements in the empty 0 slots.
• Difficulty: Easy
• Companies: Amazon, Facebook, Microsoft, Bloomberg, Apple
• LeetCode: 88

Quick Sights

• Time Complexity: O(m + n). We iterate through both arrays exactly once from back to front.
• Space Complexity: O(1). The problem explicitly demands an in-place solution. We use the trailing zeros of nums1 as our buffer.
• Core Mechanism: Maintain three pointers:
  1. p1 starting at the last actual element of nums1 (m - 1).
  2. p2 starting at the last element of nums2 (n - 1).
  3. p starting at the very end of nums1 (m + n - 1), marking the current write position. Compare nums1[p1] and nums2[p2]. Write the larger of the two to nums1[p]. Decrement p and the pointer of the array you just wrote from.

Concept Explanation

As a senior engineer, the leap in logic here is recognizing that empty buffer space at the end of an array is a massive hint to process backwards.

1. The Overwrite Danger: If you start from index 0, nums2[0] might be smaller than nums1[0]. If you write nums2[0] into nums1[0], you have permanently destroyed data you still need to evaluate. To do this from the front, you would need to allocate an entirely new $O(m+n)$ array.
2. The Safe Zone: Look at the end of nums1. It contains $n$ zeros. This is your safe zone. Because both arrays are sorted in ascending order, the absolute largest elements must be at their respective tails (m-1 and n-1).
3. The Backward Merge: Since you know the largest elements are at the tails, you can safely grab the largest element between nums1 and nums2 and drop it into the absolute last slot of nums1 (m+n-1), which is safely filled with a useless 0.
4. The Termination: You continue this process until p2 runs out of bounds (drops below 0). If p1 runs out first, you still have elements in nums2 left to copy. If p2 runs out first, you are done—the rest of nums1 is already perfectly sorted in place!

Diagram

This flowchart traces the three-pointer logic merging backwards into the buffer.

Study Pattern (SDE3+)

• 0–3 min: Immediately point out that the $O(1)$ space requirement + the trailing zeros explicitly dictates a backward traversal. Explain the overwrite danger of forward traversal.
• Implementation pass: The while loop condition only needs to be p2 >= 0. You do not need to check p1 >= 0 as the main loop condition because if p1 finishes first, you just copy the rest of p2. If p2 finishes first, p1 is already sitting in its correct, sorted position!
• 5 min extension: What if nums1 didn't have the buffer space at the end? You'd be forced into $O(n)$ space allocation. Alternatively, if this was a Linked List instead of an Array (LeetCode 21), you would merge forward because Linked Lists don't suffer from array overwrite problems (you just adjust pointers).

Approaches

• Brute force — Append nums2 to the end of nums1 (ignoring the zeros), then sort() the whole thing. Time: $O((m+n) \log(m+n))$, Space: $O(1)$ (or $O(m+n)$ depending on sort implementation). Suboptimal.
• Forward Merge with Extra Array — Merge into a new array from the front, then copy back. Time: $O(m+n)$, Space: $O(m+n)$. Suboptimal.
• Backward Merge (Three Pointers) — Time: $O(m+n)$, Space: $O(1)$. (Always pick this)

Optimal Solution

Go

func merge(nums1 []int, m int, nums2 []int, n int) {
	// Initialize pointers starting from the back
	p1 := m - 1
	p2 := n - 1
	p := m + n - 1

	// We only care about exhausting nums2.
	// If nums1 exhausts first, we still need to copy the rest of nums2.
	// If nums2 exhausts first, nums1 is already perfectly sorted in place.
	for p2 >= 0 {
		// If p1 is valid and points to a larger number, place it at p
		if p1 >= 0 && nums1[p1] > nums2[p2] {
			nums1[p] = nums1[p1]
			p1--
		} else {
			// Otherwise, place nums2's number at p
			nums1[p] = nums2[p2]
			p2--
		}
		p--
	}
}

JavaScript

function merge(nums1, m, nums2, n) {
	let p1 = m - 1;
	let p2 = n - 1;
	let p = m + n - 1;

	while (p2 >= 0) {
		if (p1 >= 0 && nums1[p1] > nums2[p2]) {
			nums1[p] = nums1[p1];
			p1--;
		} else {
			nums1[p] = nums2[p2];
			p2--;
		}
		p--;
	}
}

Walkthrough

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Loop terminates because p2 becomes -1. (Notice nums1[0] and nums1[1] were never touched because they were already in the correct place!).

Edge Cases

• n == 0 (nums2 is empty). The loop condition p2 >= 0 fails instantly, nums1 is unchanged, which is correct.
• m == 0 (nums1 is technically empty, just 0s buffer). p1 starts at -1. The p1 >= 0 condition fails, so it safely copies all of nums2 directly into nums1.

Pitfalls

• Using while (p1 >= 0 && p2 >= 0). If you do this, you must write a second loop afterward to catch any remaining elements in nums2. (You don't need a catch loop for nums1 because they are already in nums1). The single while (p2 >= 0) condition is cleaner.
• Confusing m and n as the physical array lengths. len(nums1) is m+n. m is just the logical count of valid elements.

Similar Problems

• 021. Merge Two Sorted Lists — The exact same problem, but applied to Linked Lists.
• 026. Remove Duplicates from Sorted Array — Two pointer overwrite logic.
• 977. Squares of a Sorted Array — Another problem that requires building the result array starting from the back.

Mind-Map Tags

#arrays #two-pointers #backward-sweep #in-place #merge