88 - Merge Sorted Array

Difficulty: Easy | Pattern: Two Pointers (Merge from End) | Company tags: Facebook, Amazon, Microsoft, Google

Problem Statement

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums2 into nums1 as one sorted array in-place.

The final sorted array should be stored in nums1. Note that nums1 has length m + n, with the last n elements set to 0 as placeholders.

Example 1:

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

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Approach: Merge from the End — O(m+n), O(1) space

Key insight: Merge from the back. The zeros at the end of nums1 are placeholder space. Using three pointers starting at the last elements, we place the larger value at the end without overwriting unprocessed elements.

def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    p1 = m - 1        # last valid element in nums1
    p2 = n - 1        # last element in nums2
    write = m + n - 1 # write position (back of nums1)
    
    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[write] = nums1[p1]
            p1 -= 1
        else:
            nums1[write] = nums2[p2]
            p2 -= 1
        write -= 1
    # If p1 >= 0, those elements are already in place

Algorithm Flow

Why Merge from Back?

Merging from the front would require shifting elements, making it O(m×n). From the back, we use the zero-padded slots as our working buffer — no shifts needed.

Dry Run

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

p1	p2	write	nums1[p1] vs nums2[p2]	Action
2	2	5	3 vs 6	nums1[5]=6, p2=1
2	1	4	3 vs 5	nums1[4]=5, p2=0
2	0	3	3 vs 2	nums1[3]=3, p1=1
1	0	2	2 vs 2	nums1[2]=2, p2=-1

p2 < 0 → stop. nums1 = [1,2,2,3,5,6] ✓

Edge Cases

• n = 0 → nothing to merge, nums1 already sorted
• m = 0 → copy all of nums2 into nums1 (p1=-1 throughout, always takes nums2 branch)
• All nums2 elements larger → all go at the end
• All nums2 elements smaller → once p1 exhausted, copy remaining nums2 in order

Complexity

• Time: O(m + n)
• Space: O(1) — in-place, no extra array

Common mistake: Merging from the front and writing into existing elements of nums1, which overwrites values you still need. Always merge from the end for in-place merge problems.

Key Terms

Term	Definition
Two pointers (merge from end)	Using pointers at the tail of each array/section to fill a buffer backward, avoiding overwrites and shifts.
In-place merge	Combining two sorted sequences into one without allocating a new array.
Placeholder slots	Pre-allocated zero slots at the end of nums1 that serve as working space during the merge.
Stable merge order	Using > (not >=) when comparing ensures equal elements from nums2 are placed correctly relative to nums1.

FAQ

1. Can this be solved without extra space? Yes — merging from the back is the O(1)-space technique; it reuses the zero-padded tail of nums1 as the write buffer instead of allocating a new array.
2. What if nums2 is empty (n = 0)? The while loop condition p2 >= 0 is false immediately, so the loop never runs and nums1 is left untouched — already correctly sorted.
3. What if nums1's real elements are exhausted first (m = 0)? p1 starts at -1, so p1 >= 0 is always false, meaning every iteration takes the nums2 branch and copies nums2 directly into nums1.
4. What if the arrays were merged from the front instead? You'd need to shift existing elements right to make room, degrading to O(m×n) time (or requiring an auxiliary array of size m+n for O(m+n) time but O(m+n) space).
5. What's the common follow-up interviewers ask? "How would you merge k sorted arrays?" — this generalizes to a min-heap based k-way merge, or "merge two sorted linked lists," which uses the same two-pointer idea without needing to merge from the back since there's no shifting concern.

Quick Revision

• Pattern: Two Pointers, merging from the end (back) of the array.
• Three pointers: p1 (end of real nums1 data), p2 (end of nums2), write (end of combined array).
• Compare nums1[p1] and nums2[p2]; place the larger at write, decrement that pointer and write.
• Loop while p2 >= 0 — once nums2 is exhausted, remaining nums1 elements are already in correct position.
• Merging from the back avoids shifting elements, unlike merging from the front.
• Edge cases: n = 0 (no-op), m = 0 (copy nums2 wholesale).
• Time: O(m + n); Space: O(1) — truly in-place.
• Common mistake: merging front-to-back and overwriting unprocessed values.

Related Problems

• 21 - Merge Two Sorted Lists — same merge-two-sorted-sequences idea, applied to linked lists instead of arrays.
• 167 - Two Sum II - Input Array Is Sorted — another two-pointer technique on sorted arrays.
• Merge k Sorted Lists (LeetCode 23) — generalizes this pattern using a min-heap for k-way merging.