W
← Blog/dsaarraystwo-pointers

Merge Sorted Array — Why Merging From the Back Is the Elegant O(1) Solution

Sanjeev SharmaSanjeev Sharma
12 min read

Advertisement

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 valid elements in nums1 and nums2 respectively.

Merge nums2 into nums1 in-place so that nums1 is sorted. nums1 has a total length of m + n, where the last n positions are initialized to 0 and should be ignored. You must not allocate another array.

Example:

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

Output: [1, 2, 2, 3, 5, 6]

The trailing 0s in nums1 are placeholders, not real values. The valid portion is nums1[0..m-1].

Why This Problem Matters

LeetCode 88 is a staple in Meta, Microsoft, and Google screening rounds — not because it is hard, but because it exposes whether you truly understand in-place operations and pointer mechanics.

The naive solution takes O(m·n) time (insert elements one by one with shifts). The brute-force solution takes O(m+n) time but O(m+n) extra space (copy into a third array, sort). The optimal solution takes O(m+n) time with O(1) space, and the trick that makes it work — merging from the back — is the same logic used in the merge step of Merge Sort.

Understanding this problem means you understand:

  • How to avoid overwriting data you still need
  • The "fill from the unused end" pattern common in in-place problems
  • The foundation of one of the most important sorting algorithms ever devised

Why Merging From the Front Fails

Before explaining the correct approach, it is worth seeing exactly why the front-to-back direction breaks down. Suppose you start two pointers at the beginning of each array and write results into nums1 from index 0.

nums1 = [1, 2, 3, 0, 0, 0]   (valid: 1, 2, 3)
nums2 = [2, 5, 6]

p1 = 0, p2 = 0, write = 0

Step 1: nums1[0]=1 < nums2[0]=2, so place 1 at write=0. p1++, write++
        nums1 = [1, 2, 3, 0, 0, 0]   (no change yet, fine)

Step 2: nums1[1]=2 == nums2[0]=2, place 2 at write=1. p1++, write++
        nums1 = [1, 2, 3, 0, 0, 0]   (still fine)

Step 3: nums1[2]=3 > nums2[0]=2, place nums2[0]=2 at write=2. p2++, write++
        nums1 = [1, 2, 2, 0, 0, 0]   ← we just OVERWROTE nums1[2] which was 3!

We destroyed the value 3 before we ever compared it. From this point forward, nums1[2] is gone — the merge is corrupted. The write pointer caught up to p1 and stomped on data we had not finished reading.

This is the fundamental flaw: when you write into nums1 from the front, the write pointer chases the read pointer. They collide and you lose elements.

To avoid extra space, you need a write position that will never collide with unread data. That position is the back.

The "Merge From the Back" Insight

Here is the key observation: the largest elements in the final merged array belong at the end. And we know where the end of nums1 is — index m + n - 1.

So instead of asking "what is the smallest element to place next?", we ask "what is the largest element to place next?" We compare the last valid element of nums1 with the last element of nums2, pick the larger one, and write it at write = m + n - 1. Then we step all three pointers backward.

Why is this safe? Because we write at positions m+n-1, m+n-2, m+n-3, ... These are at or beyond the current valid content of nums1 (which only occupies indices 0..m-1). The write pointer moves left; the read pointer for nums1 also moves left — but write always stays at or ahead of the read pointer, so they never collide.

The three pointers are:

  • p1 = m - 1 — points to the last valid element in nums1
  • p2 = n - 1 — points to the last element in nums2
  • write = m + n - 1 — the next position to fill, starting from the end

Common pointer initialization mistake: Many candidates initialize p1 = m and p2 = n instead of m-1 and n-1. Arrays are 0-indexed. nums1[m] is a trailing zero, not the last valid element. Always initialize to m-1 and n-1.

Handling Remaining Elements

After the main loop, one of two things has happened:

Case 1: p2 < 0 (nums2 is exhausted). This means all elements from nums2 have been placed. The remaining elements in nums1[0..p1] are already in the correct positions — they are the smallest elements and they are already in nums1. We are done. No action needed.

Case 2: p1 < 0 (nums1's valid portion is exhausted). There are still elements in nums2 that need to be copied. We loop while p2 >= 0 and copy nums2[p2] to nums1[write], decrementing both. This is the only cleanup step needed.

Common mistake: Forgetting the while p2 >= 0 tail copy. If nums2 = [1, 2] and nums1 = [3, 0, 0], after the main loop p1 goes to -1 immediately and you still have two elements from nums2 to place. Without the tail copy, the result is wrong.

Visual Dry Run

Let us trace nums1 = [1, 2, 3, 0, 0, 0] (m=3) and nums2 = [2, 5, 6] (n=3) step by step.

Initial state:

nums1 = [1, 2, 3, 0, 0, 0]
         ^p1=2
nums2 = [2, 5, 6]
                ^p2=2
write = 5

Step 1: nums1[2]=3 vs nums2[2]=6 → 6 is larger → place 6 at write=5, p2--, write--

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

Step 2: nums1[2]=3 vs nums2[1]=5 → 5 is larger → place 5 at write=4, p2--, write--

nums1 = [1, 2, 3, 0, 5, 6]
         ^p1=2
nums2 = [2, 5, 6]
         ^p2=0
write = 3

Step 3: nums1[2]=3 vs nums2[0]=2 → 3 is larger → place 3 at write=3, p1--, write--

nums1 = [1, 2, 3, 3, 5, 6]
            ^p1=1
nums2 = [2, 5, 6]
         ^p2=0
write = 2

Step 4: nums1[1]=2 vs nums2[0]=2 → equal, take from nums2 → place 2 at write=2, p2--, write--

nums1 = [1, 2, 2, 3, 5, 6]
            ^p1=1
nums2 = [2, 5, 6]
p2 = -1 (exhausted)
write = 1

p2 is now -1, so the loop ends. The remaining element 1 in nums1[0] and nums1[1] are already in place. Final result: [1, 2, 2, 3, 5, 6]. Correct.

Notice at no point did the write pointer touch a position that p1 had not already read or passed. That is the invariant that makes this approach correct.

Common Mistakes

Mistake 1 — Wrong pointer initialization. Using p1 = m instead of p1 = m - 1. nums1[m] is a 0 placeholder. Start at the last valid index.

Mistake 2 — Forgetting the tail copy for nums2. If nums2 has smaller elements than everything in nums1, the main loop exhausts p1 first, and you must manually copy the remaining nums2 elements.

Mistake 3 — Copying remaining nums1 unnecessarily. The symmetric "copy remaining nums1" loop is not needed. When p2 is exhausted, whatever is left in nums1[0..p1] is already in its final position. Adding an extra copy loop here can produce incorrect results.

Mistake 4 — Off-by-one on the loop condition. The main loop should continue while p1 >= 0 AND p2 >= 0. Breaking when either hits -1 is correct. The tail copy only covers the p2 case.

Solutions

Naive Approach — Extra Space (O(m+n) time, O(m+n) space)

Copy nums1's valid elements, then perform the standard two-pointer merge into nums1.

Python

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # Copy the valid portion of nums1 so we have a clean source
        nums1_copy = nums1[:m]
        
        p1, p2, write = 0, 0, 0
        
        # Merge from the front — safe because we read from nums1_copy, not nums1
        while p1 < m and p2 < n:
            if nums1_copy[p1] <= nums2[p2]:
                nums1[write] = nums1_copy[p1]
                p1 += 1
            else:
                nums1[write] = nums2[p2]
                p2 += 1
            write += 1
        
        # Copy leftover elements from whichever array remains
        while p1 < m:
            nums1[write] = nums1_copy[p1]
            p1 += 1
            write += 1
        
        while p2 < n:
            nums1[write] = nums2[p2]
            p2 += 1
            write += 1

JavaScript

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void}
 */
function merge(nums1, m, nums2, n) {
    // Preserve the valid portion of nums1 before we overwrite it
    const nums1Copy = nums1.slice(0, m);
    
    let p1 = 0, p2 = 0, write = 0;
    
    // Standard front-to-front merge — safe because source is nums1Copy
    while (p1 < m && p2 < n) {
        if (nums1Copy[p1] <= nums2[p2]) {
            nums1[write++] = nums1Copy[p1++];
        } else {
            nums1[write++] = nums2[p2++];
        }
    }
    
    // Drain remaining elements from either array
    while (p1 < m) nums1[write++] = nums1Copy[p1++];
    while (p2 < n) nums1[write++] = nums2[p2++];
}

Optimal Approach — Merge From the Back (O(m+n) time, O(1) space)

Python

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # p1: last valid index in nums1
        # p2: last index in nums2
        # write: next position to fill (start from the very end of nums1)
        p1, p2, write = m - 1, n - 1, m + n - 1
        
        # Compare largest unplaced elements from each array;
        # the bigger one goes to the current write position
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[write] = nums1[p1]
                p1 -= 1
            else:
                nums1[write] = nums2[p2]
                p2 -= 1
            write -= 1
        
        # If nums2 still has elements, copy them over.
        # If nums1 still has elements, they are already in place — nothing to do.
        while p2 >= 0:
            nums1[write] = nums2[p2]
            p2 -= 1
            write -= 1

JavaScript

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void}
 */
function merge(nums1, m, nums2, n) {
    // Start all three pointers at their rightmost valid positions
    let p1 = m - 1;       // last real element in nums1
    let p2 = n - 1;       // last element in nums2
    let write = m + n - 1; // last slot in nums1 (the full length)
    
    // Place the larger of the two current candidates at write, move backward
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[write--] = nums1[p1--];
        } else {
            // Also handles the equal case — take from nums2 first
            nums1[write--] = nums2[p2--];
        }
    }
    
    // Drain remaining nums2 elements if nums1's valid portion ran out first.
    // Remaining nums1 elements need no action — they are already in place.
    while (p2 >= 0) {
        nums1[write--] = nums2[p2--];
    }
}

Complexity Analysis

ApproachTimeSpaceNotes
Naive (extra copy)O(m + n)O(m)Copies valid nums1; then standard merge
Optimal (from back)O(m + n)O(1)Each element visited exactly once

The optimal approach is O(m+n) because p1 moves from m-1 to some point ≥ -1, and p2 moves from n-1 to -1. Each element is written to nums1 exactly once. The write pointer decrements in lockstep, so we visit at most m+n positions total.

Connection to Merge Sort

The merge step in Merge Sort does exactly this — it takes two sorted halves and produces one sorted array. In the textbook version, you copy both halves into auxiliary arrays and then merge back in O(m+n) time and O(m+n) space. LeetCode 88 is a constrained version of that merge step: you can only use the extra space already present in nums1.

The insight that unlocks the in-place version — that you can fill from the back without collision — is one of the rare tricks that makes an O(n) extra-space operation into an O(1) one. Recognizing this pattern is a mark of strong algorithmic intuition.

Follow-up Questions

21. Merge Two Sorted Lists — Same idea, but with linked list nodes instead of array indices. Instead of writing to a slot, you update next pointers. The comparison logic is identical.

23. Merge k Sorted Lists — Generalize to k lists. The naive approach calls the two-list merge repeatedly (O(kN) total). The optimal approach uses a min-heap to always extract the smallest current head across all k lists, achieving O(N log k).

349. Intersection of Two Arrays — Use two pointers on two sorted arrays, advancing the smaller one. When both pointers point to equal values, record the intersection. Same pointer-on-sorted-arrays pattern.

Sort Array By Parity (LC 905) — Another in-place two-pointer problem where you fill from both ends simultaneously. The "fill from the correct end" mindset is the same.

This Pattern Solves

Whenever you see "merge two sorted sequences in-place" or "fill an array from the end to avoid overwrite," the three-pointer-from-the-back approach applies. You will find it in:

  • Merge sort's merge subroutine
  • Interval merging (sort + compare adjacent intervals)
  • Dutch National Flag (three-way partition, filling from both ends)
  • External merge sort (merging sorted file chunks)

The unifying principle: if your write target overlaps your read source, find a direction where the write pointer can never catch the read pointer.

Key Takeaway

Merging from the back works because the trailing zeros in nums1 give you safe "write space" that your read pointers never reach. Starting p1 at m-1 and p2 at n-1, you always place the globally largest remaining element at the rightmost unfilled position — and by the time the write pointer reaches a slot that p1 points to, p1 has already moved past it. This O(1)-space trick is the same elegance at the heart of Merge Sort's merge step, and mastering it gives you a template for an entire family of two-pointer merge problems.

Next: Problem 8 — Remove Duplicates from Sorted Array →

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro

twitterlinkedingithubmail

← Previous

Remove Duplicates from Sorted Array — Write Pointer Pattern Explained [Easy]

Next →

Plus One — Mastering Carry Propagation in Arrays (LeetCode 66)