Merge Sorted Array

EasyTwo Pointers · Merge from the Back🧩 Two Pointers LeetCode #88 ↗Updated Oct 30, 2026

Problem

Two arrays are sorted in non-decreasing order: nums1 holds m real values followed by n placeholder zeros, and nums2 holds n values. Merge nums2 into nums1 in-place so that all m + n slots end up sorted. Nothing is returned.

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

Inputnums1 = [1], m = 1, nums2 = [], n = 0Output[1]

Inputnums1 = [0], m = 0, nums2 = [1], n = 1Output[1]

0 ≤ m, n ≤ 200 · 1 ≤ m + n · -10⁹ ≤ values ≤ 10⁹ · Follow-up: O(m + n) time.

Try it yourself

Java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The free space sits at the end of nums1. Fill it from the back with the larger of the two current tails — the write pointer can never overtake an unread value of nums1.

PatternTwo Pointers

Instinct Sorted input, a pair/triple hitting a target, or something symmetric? Put one pointer at each end and move the one that can only improve things.

Memory hack Squeeze from both ends - every step throws away a whole row of the brute-force grid.

Open the Two Pointers guide →

Approaches

Brute ForceAppend, then Sort

Time O((m+n) log(m+n))Space O(log(m+n))

Copy nums2 into the placeholder slots and sort the whole array. Correct because the final content is just the union of both arrays in order; the space is the sort's recursion stack.

Java

public void merge(int[] nums1, int m, int[] nums2, int n) {
    for (int i = 0; i < n; i++) {
        nums1[m + i] = nums2[i];
    }
    Arrays.sort(nums1);
}

Two lines, but ignores that both halves are already sorted.

BetterCopy Prefix, Merge Forward

Time O(m + n)Space O(m)

A front-to-back merge would overwrite values of nums1 before they are read, so first save the m real values in a copy. Then do the classic two-pointer merge from the copy and nums2 into nums1.

Java

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] first = Arrays.copyOf(nums1, m); // protect the real values
    int i = 0, j = 0, w = 0;
    while (i < m && j < n) {
        nums1[w++] = (first[i] <= nums2[j]) ? first[i++] : nums2[j++];
    }
    while (i < m) nums1[w++] = first[i++];
    while (j < n) nums1[w++] = nums2[j++];
}

Linear time, but needs an O(m) buffer.

OptimalThree Pointers from the End

Time O(m + n)Space O(1)

Pointers i and j start at the last real element of each array; w starts at the last slot. Place the larger tail at w and step back. Since w = i + j + 1, the write position is always right of i, so nothing unread is clobbered.

Java

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, w = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[w--] = nums1[i--];
        } else {
            nums1[w--] = nums2[j--];
        }
    }
    // leftover nums1 values are already in place
}

Dry runnums1 = [1,2,3,0,0,0], nums2 = [2,5,6]

i nums1 tailw write changed

start
1

2

3
i
0

0

0
w
j → 6
step 1
1

2

3
i
0

0
w
6

6 > 3: take 6
step 2
1

2

3
i
0
w
5

6

5 > 3: take 5
step 3
1

2
i
3
w
3

5

6

3 > 2: take 3
step 4
1

2
i w
2

3

5

6

tie: take nums2's 2
done
1

2

2

3

5

6

j < 0 → stop ✔

Linear, in-place, and stops as soon as nums2 is used up.

Pro tip

Loop on j >= 0, not on i: once nums2 is empty the remaining nums1 prefix is already correct.

At a glance

Level	Approach	Time	Space
Brute Force	Append, then Sort	`O((m+n) log(m+n))`	`O(log(m+n))`
Better	Copy Prefix, Merge Forward	`O(m + n)`	`O(m)`
Optimal	Three Pointers from the End	`O(m + n)`	`O(1)`

Common pitfalls

Merging front-to-back in place — overwrites nums1 values before reading them.
Forgetting the i >= 0 guard when m = 0 (index -1).
Returning a new array — the result must live in nums1.

Interview tips

Point out where the free space is: that is the hint to merge backwards.
Explain why w never passes i (w - i = j + 1 > 0).
Mention that leftover nums1 elements need no copying.

Pattern

Reverse two-pointer merge → merge sorted data in-place when the spare room is at the end of the destination.

My notes saved in this browser