Loading…

easyArraysLC #88Frequently asked

Merge Sorted Array

Q: How do you solve Merge Sorted Array using the Copy and Sort (Naive) approach?

When to use it: Say it first to show you have a working baseline — then immediately note it ignores the sorted inputs and the free space. The most literal way to satisfy the spec: physically place all the data in one array, then sort it. Copy `nums2[j]` into `nums1[m + j]` for each `j`, so the trailing zero region now holds `nums2`'s values, and finish with a library sort over the whole length. **Why this is the natural first attempt.** The problem says *"store the result inside nums1"*. The simplest reading is: get every value into `nums1` somehow, then make `nums1` sorted. We don't have to think about merge logic at all — we lean on the sorting routine to do the ordering for us. It's correct, it's short, and it's a fine sanity-check answer to state out loud. **Why it leaves value on the table.** Both inputs arrive *already sorted*. A general-purpose sort throws that information away and re-discovers the order from scratch at `O((m+n)log(m+n))`. A merge exploits the existing order and runs in `O(m+n)` — strictly better. Whenever you sort data that's already partially ordered, an interviewer hears *"I didn't use the structure I was given."* **Why the copy targets `m + j`.** The first `m` slots hold real data we must not clobber, and the next `n` slots are the zeros. Writing `nums2[j]` to `nums1[m + j]` drops each `nums2` value neatly into the padding region, so after the copy `nums1` contains exactly the `m+n` values we need — just unsorted across the seam. **Why we don't ship this.** It works and even passes the judge, but the entire point of the problem is the in-place linear merge. Mention this as your baseline, state its `log` factor, and then reach for three pointers. Time complexity: O((m+n)log(m+n)). Space complexity: O(1).

LCPractice

Two Pointers · 5 of 30 · 9 min

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 nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements are the ones that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

In plain English

nums1 is over-allocated: its real data is the first m slots, and the last n slots are padding zeros that exist only to give us room. We must end with nums1 holding all m+n values in sorted order — in place, no return value.

Examples

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]
Note: Merging [1,2,3] and [2,5,6] gives [1,2,2,3,5,6], written back into nums1.

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Note: nums2 is empty, so nums1 is already the answer — the loop never runs.

Example 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Note: nums1 has no real elements; the single value from nums2 fills the only slot.

Constraints

nums1.length == m + n
nums2.length == n
0 ≤ m, n ≤ 200
1 ≤ m + n ≤ 200
-10⁹ ≤ nums1[i], nums2[j] ≤ 10⁹

Clarifying questions4First question: Are both arrays guaranteed sorted on entry?Explore questions

Q1.Are both arrays guaranteed sorted on entry?
Yes, both are non-decreasing. That's what makes a linear merge possible — if they weren't, we'd have to sort.
Q2.Is the trailing space in nums1 always exactly n zeros?
Yes. nums1.length == m + n by definition, and the last n entries are placeholders to ignore. Use m and n, not nums1.length.
Q3.Can m or n be zero?
Yes. If n == 0 there's nothing to merge; if m == 0, nums1 should just become a copy of nums2. The back-to-front loop handles both naturally.
Q4.Must the result be O(1) extra space?
It's the expected answer. Copy-and-sort passes the judge but signals you missed the in-place merge the problem is built to test.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Merge nums2 into nums1 in place. The naive answer copies both into a buffer and sorts (O((m+n)log(m+n))); the canonical answer merges from the BACK with three pointers (i=m−1, j=n−1, k=m+n−1), writing the larger element into the tail so you never overwrite an unread value in nums1.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you notice that front-to-back merging overwrites unread data in nums1, and pivot to filling from the back — the insight that makes O(1) space possible.

Where candidates slip

Merging front-to-back into nums1, clobbering values you haven't compared yet, or looping on nums1.length (which includes the padding zeros) instead of m.

How to stand out

State the naive copy-and-sort, explain why a forward merge corrupts nums1, then derive the back-to-front pointers and note the loop can stop once nums2 is drained.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Copy and Sort (Naive)	`O((m+n)log(m+n))`	`O(1)`	Say it first to show you have a working baseline — then immediately note it ignores the sorted inputs and the free space.	Read
2	Three Pointers, Back to Front (Optimal)Optimal	`O(m+n)`	`O(1)`	The answer they want. Frame it as 'fill the tail with the larger element so we never overwrite unread data'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMerge nums2 into nums1 which has trailing free spaceFill which direction?Front to backBack to frontExplore the full tree

Filling nums1 from the backnums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

How to read it:i scans nums1's real data, j scans nums2, k is the write head at the tail. The larger candidate is written into k each step.

Frame 1
i=2, j=2, k=5
nums1[2]=3 vs nums2[2]=6 → 6 larger → write 6
1
[0]
2
[1]
i↓j↓
3
[2]
_
[3]
_
[4]
k↓
6
[5]
Frame 2
i=2, j=1, k=4
nums1[2]=3 vs nums2[1]=5 → 5 larger → write 5
1
[0]
j↓
2
[1]
i↓
3
[2]
_
[3]
k↓
5
[4]
6
[5]
Frame 3
i=2, j=0, k=3
nums1[2]=3 vs nums2[0]=2 → 3 larger → write 3
j↓
1
[0]
i↓
2
[1]
3
[2]
k↓
3
[3]
5
[4]
6
[5]
Frame 4
i=1, j=0, k=2
nums1[1]=2 vs nums2[0]=2 → take nums2's 2 → write 2
1
[0]
i↓
2
[1]
k↓
2
[2]
3
[3]
5
[4]
6
[5]
Frame 5
j exhausted
nums2 drained → nums1's leftover [1,2] already in place → done
1
[0]
k↓
2
[1]
2
[2]
3
[3]
5
[4]
6
[5]

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Copy and Sort (Naive)

TimeO((m+n)log(m+n))SpaceO(1)

Say it first to show you have a working baseline — then immediately note it ignores the sorted inputs and the free space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already have all m+n values living in nums1 (the real ones up front, zeros at the back). What if you just put nums2's values into those zero slots?

2Hint 2Explore hint

Copy each nums2[j] into nums1[m + j], so all m+n values sit in nums1.

3Hint 3Explore hint

Now nums1 holds everything but out of order — call a standard sort and let it fix the arrangement.

A · Core idea

The most literal way to satisfy the spec: physically place all the data in one array, then sort it. Copy nums2[j] into nums1[m + j] for each j, so the trailing zero region now holds nums2's values, and finish with a library sort over the whole length.

Why this is the natural first attempt. The problem says "store the result inside nums1". The simplest reading is: get every value into nums1 somehow, then make nums1 sorted. We don't have to think about merge logic at all — we lean on the sorting routine to do the ordering for us. It's correct, it's short, and it's a fine sanity-check answer to state out loud.

Why it leaves value on the table. Both inputs arrive already sorted. A general-purpose sort throws that information away and re-discovers the order from scratch at O((m+n)log(m+n)). A merge exploits the existing order and runs in O(m+n) — strictly better. Whenever you sort data that's already partially ordered, an interviewer hears "I didn't use the structure I was given."

Why the copy targets `m + j`. The first m slots hold real data we must not clobber, and the next n slots are the zeros. Writing nums2[j] to nums1[m + j] drops each nums2 value neatly into the padding region, so after the copy nums1 contains exactly the m+n values we need — just unsorted across the seam.

Why we don't ship this. It works and even passes the judge, but the entire point of the problem is the in-place linear merge. Mention this as your baseline, state its log factor, and then reach for three pointers.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

copy j=0

nums1[3] = nums2[0] = 2

State[1,2,3,2,0,0]

Final result[1,2,2,3,5,6]

C · Code with teaching comments

Reference implementation previewpublic void merge(int[] nums1, int m, int[] nums2, int n) { for (int j = 0; j < n; j++) { nums1[m + j] = nums2[j]; } Arrays.sort(nums1);Explore the full code

solution.javaJava

Copy and Sort (Naive) — reference

2 teaching notes

1
public void merge(int[] nums1, int m, int[] nums2, int n) {
2
    for (int j = 0; j < n; j++) {
3
        // Drop each nums2 value into the trailing zero region, starting at index m.
4
        nums1[m + j] = nums2[j];
5
    }
6
    // Sorts all m+n values — this is the O((m+n)log(m+n)) step that ignores the
7
    // existing order.
8
    Arrays.sort(nums1);
9
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.9 lines

D · Why it works and complexityO((m+n)log(m+n)) timeO(1) spaceOpen the invariant and proofExplore the proof

The sorted-ness of the inputs is the gift the problem hands you. Any solution that calls a comparison sort is implicitly admitting it ignored that gift — a strong cue to look for a linear merge instead.

ComplexityO((m+n)log(m+n)) time, O(1) space — Copying nums2 is O(n); the dominating cost is sorting m+n elements at O((m+n)log(m+n)). The sort is in-place (Java's dual-pivot quicksort on primitives, Python's Timsort), so no asymptotic extra space beyond the call stack.

E · Edge cases and pitfalls5n = 0 — The copy loop never runs; sort over the already-sorted m elements is a no-op cost.Explore edge cases

Edge cases handled

n = 0The copy loop never runs; sort over the already-sorted m elements is a no-op cost.
m = 0All n values are copied to indices 0..n-1, then sorted — equivalent to copying nums2.

Pitfalls

Looping the copy to n but writing to nums1[j] instead of nums1[m + j] — overwrites real data.
Sorting only part of the array (e.g. Arrays.sort(nums1, 0, m)) — leaves nums2's values unsorted.
Mentioning only this approach — interviewers want the O(m+n) merge.

03.2

Approach 2 of 2 · Optimal

Three Pointers, Back to Front (Optimal)

TimeO(m+n)SpaceO(1)

The answer they want. Frame it as 'fill the tail with the larger element so we never overwrite unread data'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A forward merge into nums1 would overwrite nums1's own unread values. Where in nums1 is there guaranteed-empty space you can safely write into right now?

2Hint 2Explore hint

The free slots are at the END of nums1. So fill from the back: keep a write pointer k at index m+n-1 and compare the current largest of each array.

3Hint 3Explore hint

Use i = m-1, j = n-1, k = m+n-1. At each step write the larger of nums1[i] and nums2[j] into nums1[k], decrement that source pointer and k. Stop when j hits -1; remaining nums1 values are already in place.

A · Core idea

Walk both arrays from their high ends and fill nums1 from its high end. Keep i = m−1 (last real value in nums1), j = n−1 (last value in nums2), and k = m+n−1 (the final slot). At each step copy the larger of nums1[i] and nums2[j] into nums1[k], then step that source pointer and k back by one.

Why back-to-front is the whole trick. Picture a forward merge writing into nums1[0], nums1[1], … The very first write could land on nums1[0], a value we still need to compare later — we'd destroy input before reading it, which is exactly why a naive in-place forward merge is impossible without a buffer. Now flip direction. The slots from index m to m+n−1 are padding — nothing real lives there. If we always write the current largest remaining value into the highest empty slot, the write head k stays strictly ahead of (to the right of) both read heads i and j. Every slot we overwrite is one we've already consumed or one that was padding to begin with. That positional guarantee is what makes O(1) space possible.

Why we compare and take the larger. We're constructing the sorted array from its largest element down. The largest unplaced value must be one of the two current candidates at the read heads (everything to their left is smaller, since both arrays are sorted). So nums1[k] should receive max(nums1[i], nums2[j]), and we retreat the pointer we drew from. Filling largest-first is the mirror image of a normal forward merge that fills smallest-first.

Why the loop ends when `j` reaches −1. Two cases at termination. If nums1 empties first (i < 0) while nums2 still has values, we must keep copying nums2's remaining values down — so the loop has to continue while j >= 0. But if nums2 empties first (j < 0), every remaining nums1 value is already sitting in its correct position at the front of nums1 — they were never moved, so there's nothing left to do. That asymmetry is why the canonical loop condition is while (j >= 0) and why the i >= 0 test lives inside the comparison: it stops us from reading nums1[-1] once nums1 is exhausted.

Why this beats copy-and-sort. No auxiliary array, no log factor — each value is touched once. It's the textbook merge step of merge sort, specialised to reuse nums1's tail as the output buffer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

start

i=2 (val 3), j=2 (val 6), k=5 (empty)

[0]

[1]

i ↓j ↓

[2]

[3]

[4]

k ↓

[5]

Current pointerResolved stateNot processed

Final result[1,2,2,3,5,6]

C · Code with teaching comments

solution.javaJava

Three Pointers, Back to Front (Optimal) — optimal

4 teaching notes

1
public void merge(int[] nums1, int m, int[] nums2, int n) {
2
    int i = m - 1;
3
    int j = n - 1;
4
    // Write head starts at the LAST slot — the free space is at the tail, so we fill
5
    // backwards.
6
    int k = m + n - 1;
7
    // Loop until nums2 is drained; leftover nums1 values are already in their correct
8
    // positions.
9
    while (j >= 0) {
10
        // Guard i >= 0 so we never read nums1[-1] after nums1 empties; take the LARGER
11
        // candidate.
12
        if (i >= 0 && nums1[i] > nums2[j]) {
13
            // Place the larger value at the tail and retreat both the source and write
14
            // pointers.
15
            nums1[k--] = nums1[i--];
16
        } else {
17
            nums1[k--] = nums2[j--];
18
        }
19
    }
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(m+n) timeO(1) spaceOpen the invariant and proofExplore the proof

The free space lives at the back, so write at the back. The deeper, reusable idea: when you must overwrite an array in place, choose a fill direction where your write pointer can never collide with an unread read pointer. Here that direction is right-to-left; in other shifting problems it might be left-to-right — the principle is the same.

ComplexityO(m+n) time, O(1) space — Each of the m+n slots is written exactly once and each comparison is O(1), so total work is O(m+n). We only use a handful of index variables → O(1) extra space.

E · Edge cases and pitfalls7nums1 = [0], m = 0, nums2 = [1], n = 1 — i starts at -1, so the i>=0 guard fails and every write comes from nums2 → nums1 becomes [1].Explore edge cases

Edge cases handled

nums1 = [0], m = 0, nums2 = [1], n = 1i starts at -1, so the i>=0 guard fails and every write comes from nums2 → nums1 becomes [1].
nums1 = [2,0], m = 1, nums2 = [1], n = 1k=1: 2 > 1 → nums1[1]=2; k=0, j=0: write 1 → [1,2].
n = 0j starts at -1, the while loop never executes, nums1 is left untouched (already correct).

Pitfalls

Filling front-to-back into nums1 — overwrites unread values and needs a buffer.
Forgetting the i >= 0 guard — crashes or wraps when nums1 empties before nums2.
Using nums1.length instead of m+n-1 for k — they're equal here, but relying on the padding region's size in other ways is fragile.
Stopping the loop when i < 0 instead of when j < 0 — drops the remaining nums2 values.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; int j = n - 1; int k = m + n - 1; while (j >= 0) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forward merge overwrites unread data

Writing the merged result into nums1 starting at index 0 stomps on nums1's own values before they're compared. The first write to nums1[0] can destroy a value you still need.

Explore the code comparison

Don't write this

int i = 0, j = 0, k = 0;
while (j < n) {
    if (i < m && nums1[i] <= nums2[j]) {
        nums1[k++] = nums1[i++]; // corrupts nums1 ahead of i
    } else {
        nums1[k++] = nums2[j++];
    }
}

Write this instead

int 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--];
    }
}

Missing the i >= 0 guard

When nums1 runs out first, i becomes -1. Reading nums1[i] then indexes nums1[-1] — a crash in Java, a wrap-around read in Python. The guard must be checked before the comparison.

Explore the code comparison

Don't write this

while j >= 0:
    if nums1[i] > nums2[j]:   # nums1[-1] once i < 0
        nums1[k] = nums1[i]; i -= 1
    else:
        nums1[k] = nums2[j]; j -= 1
    k -= 1

Write this instead

while j >= 0:
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[k] = nums1[i]; i -= 1
    else:
        nums1[k] = nums2[j]; j -= 1
    k -= 1

Treating padding zeros as real values

nums1.length is m+n, but only the first m entries are data. Looping over nums1.length and comparing the trailing zeros merges fake values into the result.

Explore the code comparison

Don't write this

for (int i = 0; i < nums1.length; i++) {
    // compares the padding 0s as if they were elements
}

Write this instead

int i = m - 1; // only the first m entries are real data
int j = n - 1;
int k = m + n - 1;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Three-pointer merge filled back-to-front

Code pattern to memorize

i = m-1, j = n-1, k = m+n-1
while j >= 0:
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[k] = nums1[i]; i -= 1
    else:
        nums1[k] = nums2[j]; j -= 1
    k -= 1

Rules to remember

1Fill from the back (k = m+n-1), not the front — the free space in nums1 lives at the tail.
2The loop ends when j (the nums2 pointer) is exhausted — leftover nums1 elements are already in place.
3Guard i >= 0 inside the comparison so you don't read nums1[-1] when nums1 runs out first.
4Use the real lengths m and n, not nums1.length — nums1 is padded with zeros you must ignore.
5Pick the larger of the two candidates for the tail slot, since we're filling largest-first.
6No extra array needed — this is O(1) space, which is the whole point of merging backwards.

Use this pattern when

Two **sorted** sequences that must become one sorted sequence
One container has trailing free space to absorb the other in place
You want `O(m+n)` time without an auxiliary buffer
The merge step of merge sort, or k-way merge generalisations

Choose another pattern when

Inputs are unsorted → sort first, or this trick buys nothing
No spare room in the destination → you genuinely need an output array
You need to merge thousands of lists → use a heap (k-way merge)
Order doesn't matter → just concatenate and sort

Interview takeaway

When you must merge into a buffer that already holds one of the inputs, fill from the back. Writing largest-first into the tail guarantees every slot you overwrite has already been read — this back-to-front trick is the reusable idea, and it reappears anywhere you do in-place array shifting.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical in-place merge filled back-to-front. Recognise it whenever you must combine sorted data into a buffer that already holds one input — choose the fill direction that keeps the write head clear of unread reads. Same backward-fill idea powers Squares of a Sorted Array and the merge step of merge sort.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Two Sorted Lists
Coming soon
Same merge logic on linked lists — splice nodes instead of writing array slots.
Merge k Sorted Lists
Coming soon
Generalises to k inputs — use a min-heap of the current heads, O(N log k).
Squares of a Sorted Array
Two pointers from both ends, fill the output from the back with the larger square.
Sort Colors
Coming soon
In-place partitioning with pointers — another O(1)-space array rearrangement.

Same pattern

←

Trapping Rain Water

Continue · Next problem

Remove Duplicates from Sorted Array

easyArraysLC #88Frequently asked

Merge Sorted Array

LCPractice

Two Pointers · 5 of 30 · 9 min

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 nums1 and nums2 into a single array sorted in non-decreasing order.

In plain English

Examples

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]
Note: Merging [1,2,3] and [2,5,6] gives [1,2,2,3,5,6], written back into nums1.

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Note: nums2 is empty, so nums1 is already the answer — the loop never runs.

Example 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Note: nums1 has no real elements; the single value from nums2 fills the only slot.

Constraints

nums1.length == m + n
nums2.length == n
0 ≤ m, n ≤ 200
1 ≤ m + n ≤ 200
-10⁹ ≤ nums1[i], nums2[j] ≤ 10⁹

Clarifying questions4First question: Are both arrays guaranteed sorted on entry?Explore questions

Q1.Are both arrays guaranteed sorted on entry?
Yes, both are non-decreasing. That's what makes a linear merge possible — if they weren't, we'd have to sort.
Q2.Is the trailing space in nums1 always exactly n zeros?
Yes. nums1.length == m + n by definition, and the last n entries are placeholders to ignore. Use m and n, not nums1.length.
Q3.Can m or n be zero?
Yes. If n == 0 there's nothing to merge; if m == 0, nums1 should just become a copy of nums2. The back-to-front loop handles both naturally.
Q4.Must the result be O(1) extra space?
It's the expected answer. Copy-and-sort passes the judge but signals you missed the in-place merge the problem is built to test.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you notice that front-to-back merging overwrites unread data in nums1, and pivot to filling from the back — the insight that makes O(1) space possible.

Where candidates slip

Merging front-to-back into nums1, clobbering values you haven't compared yet, or looping on nums1.length (which includes the padding zeros) instead of m.

How to stand out

State the naive copy-and-sort, explain why a forward merge corrupts nums1, then derive the back-to-front pointers and note the loop can stop once nums2 is drained.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Copy and Sort (Naive)	`O((m+n)log(m+n))`	`O(1)`	Say it first to show you have a working baseline — then immediately note it ignores the sorted inputs and the free space.	Read
2	Three Pointers, Back to Front (Optimal)Optimal	`O(m+n)`	`O(1)`	The answer they want. Frame it as 'fill the tail with the larger element so we never overwrite unread data'.	Read

Filling nums1 from the backnums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

How to read it:i scans nums1's real data, j scans nums2, k is the write head at the tail. The larger candidate is written into k each step.

Frame 1
i=2, j=2, k=5
nums1[2]=3 vs nums2[2]=6 → 6 larger → write 6
1
[0]
2
[1]
i↓j↓
3
[2]
_
[3]
_
[4]
k↓
6
[5]
Frame 2
i=2, j=1, k=4
nums1[2]=3 vs nums2[1]=5 → 5 larger → write 5
1
[0]
j↓
2
[1]
i↓
3
[2]
_
[3]
k↓
5
[4]
6
[5]
Frame 3
i=2, j=0, k=3
nums1[2]=3 vs nums2[0]=2 → 3 larger → write 3
j↓
1
[0]
i↓
2
[1]
3
[2]
k↓
3
[3]
5
[4]
6
[5]
Frame 4
i=1, j=0, k=2
nums1[1]=2 vs nums2[0]=2 → take nums2's 2 → write 2
1
[0]
i↓
2
[1]
k↓
2
[2]
3
[3]
5
[4]
6
[5]
Frame 5
j exhausted
nums2 drained → nums1's leftover [1,2] already in place → done
1
[0]
k↓
2
[1]
2
[2]
3
[3]
5
[4]
6
[5]

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Copy and Sort (Naive)

TimeO((m+n)log(m+n))SpaceO(1)

Say it first to show you have a working baseline — then immediately note it ignores the sorted inputs and the free space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already have all m+n values living in nums1 (the real ones up front, zeros at the back). What if you just put nums2's values into those zero slots?

2Hint 2Explore hint

Copy each nums2[j] into nums1[m + j], so all m+n values sit in nums1.

3Hint 3Explore hint

Now nums1 holds everything but out of order — call a standard sort and let it fix the arrangement.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

copy j=0

nums1[3] = nums2[0] = 2

State[1,2,3,2,0,0]

Final result[1,2,2,3,5,6]

C · Code with teaching comments

Reference implementation previewpublic void merge(int[] nums1, int m, int[] nums2, int n) { for (int j = 0; j < n; j++) { nums1[m + j] = nums2[j]; } Arrays.sort(nums1);Explore the full code

solution.javaJava

Copy and Sort (Naive) — reference

2 teaching notes

1
public void merge(int[] nums1, int m, int[] nums2, int n) {
2
    for (int j = 0; j < n; j++) {
3
        // Drop each nums2 value into the trailing zero region, starting at index m.
4
        nums1[m + j] = nums2[j];
5
    }
6
    // Sorts all m+n values — this is the O((m+n)log(m+n)) step that ignores the
7
    // existing order.
8
    Arrays.sort(nums1);
9
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.9 lines

D · Why it works and complexityO((m+n)log(m+n)) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5n = 0 — The copy loop never runs; sort over the already-sorted m elements is a no-op cost.Explore edge cases

Edge cases handled

n = 0The copy loop never runs; sort over the already-sorted m elements is a no-op cost.
m = 0All n values are copied to indices 0..n-1, then sorted — equivalent to copying nums2.

Pitfalls

Looping the copy to n but writing to nums1[j] instead of nums1[m + j] — overwrites real data.
Sorting only part of the array (e.g. Arrays.sort(nums1, 0, m)) — leaves nums2's values unsorted.
Mentioning only this approach — interviewers want the O(m+n) merge.

03.2

Approach 2 of 2 · Optimal

Three Pointers, Back to Front (Optimal)

TimeO(m+n)SpaceO(1)

The answer they want. Frame it as 'fill the tail with the larger element so we never overwrite unread data'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A forward merge into nums1 would overwrite nums1's own unread values. Where in nums1 is there guaranteed-empty space you can safely write into right now?

2Hint 2Explore hint

The free slots are at the END of nums1. So fill from the back: keep a write pointer k at index m+n-1 and compare the current largest of each array.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

start

i=2 (val 3), j=2 (val 6), k=5 (empty)

[0]

[1]

i ↓j ↓

[2]

[3]

[4]

k ↓

[5]

Current pointerResolved stateNot processed

Final result[1,2,2,3,5,6]

C · Code with teaching comments

solution.javaJava

Three Pointers, Back to Front (Optimal) — optimal

4 teaching notes

1
public void merge(int[] nums1, int m, int[] nums2, int n) {
2
    int i = m - 1;
3
    int j = n - 1;
4
    // Write head starts at the LAST slot — the free space is at the tail, so we fill
5
    // backwards.
6
    int k = m + n - 1;
7
    // Loop until nums2 is drained; leftover nums1 values are already in their correct
8
    // positions.
9
    while (j >= 0) {
10
        // Guard i >= 0 so we never read nums1[-1] after nums1 empties; take the LARGER
11
        // candidate.
12
        if (i >= 0 && nums1[i] > nums2[j]) {
13
            // Place the larger value at the tail and retreat both the source and write
14
            // pointers.
15
            nums1[k--] = nums1[i--];
16
        } else {
17
            nums1[k--] = nums2[j--];
18
        }
19
    }
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(m+n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7nums1 = [0], m = 0, nums2 = [1], n = 1 — i starts at -1, so the i>=0 guard fails and every write comes from nums2 → nums1 becomes [1].Explore edge cases

Edge cases handled

nums1 = [0], m = 0, nums2 = [1], n = 1i starts at -1, so the i>=0 guard fails and every write comes from nums2 → nums1 becomes [1].
nums1 = [2,0], m = 1, nums2 = [1], n = 1k=1: 2 > 1 → nums1[1]=2; k=0, j=0: write 1 → [1,2].
n = 0j starts at -1, the while loop never executes, nums1 is left untouched (already correct).

Pitfalls

Filling front-to-back into nums1 — overwrites unread values and needs a buffer.
Forgetting the i >= 0 guard — crashes or wraps when nums1 empties before nums2.
Using nums1.length instead of m+n-1 for k — they're equal here, but relying on the padding region's size in other ways is fragile.
Stopping the loop when i < 0 instead of when j < 0 — drops the remaining nums2 values.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; int j = n - 1; int k = m + n - 1; while (j >= 0) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forward merge overwrites unread data

Writing the merged result into nums1 starting at index 0 stomps on nums1's own values before they're compared. The first write to nums1[0] can destroy a value you still need.

Explore the code comparison

Don't write this

int i = 0, j = 0, k = 0;
while (j < n) {
    if (i < m && nums1[i] <= nums2[j]) {
        nums1[k++] = nums1[i++]; // corrupts nums1 ahead of i
    } else {
        nums1[k++] = nums2[j++];
    }
}

Write this instead

int 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--];
    }
}

Missing the i >= 0 guard

When nums1 runs out first, i becomes -1. Reading nums1[i] then indexes nums1[-1] — a crash in Java, a wrap-around read in Python. The guard must be checked before the comparison.

Explore the code comparison

Don't write this

while j >= 0:
    if nums1[i] > nums2[j]:   # nums1[-1] once i < 0
        nums1[k] = nums1[i]; i -= 1
    else:
        nums1[k] = nums2[j]; j -= 1
    k -= 1

Write this instead

while j >= 0:
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[k] = nums1[i]; i -= 1
    else:
        nums1[k] = nums2[j]; j -= 1
    k -= 1

Treating padding zeros as real values

nums1.length is m+n, but only the first m entries are data. Looping over nums1.length and comparing the trailing zeros merges fake values into the result.

Explore the code comparison

Don't write this

for (int i = 0; i < nums1.length; i++) {
    // compares the padding 0s as if they were elements
}

Write this instead

int i = m - 1; // only the first m entries are real data
int j = n - 1;
int k = m + n - 1;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Three-pointer merge filled back-to-front

Code pattern to memorize

i = m-1, j = n-1, k = m+n-1
while j >= 0:
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[k] = nums1[i]; i -= 1
    else:
        nums1[k] = nums2[j]; j -= 1
    k -= 1

Rules to remember

1Fill from the back (k = m+n-1), not the front — the free space in nums1 lives at the tail.
2The loop ends when j (the nums2 pointer) is exhausted — leftover nums1 elements are already in place.
3Guard i >= 0 inside the comparison so you don't read nums1[-1] when nums1 runs out first.
4Use the real lengths m and n, not nums1.length — nums1 is padded with zeros you must ignore.
5Pick the larger of the two candidates for the tail slot, since we're filling largest-first.
6No extra array needed — this is O(1) space, which is the whole point of merging backwards.

Use this pattern when

Two **sorted** sequences that must become one sorted sequence
One container has trailing free space to absorb the other in place
You want `O(m+n)` time without an auxiliary buffer
The merge step of merge sort, or k-way merge generalisations

Choose another pattern when

Inputs are unsorted → sort first, or this trick buys nothing
No spare room in the destination → you genuinely need an output array
You need to merge thousands of lists → use a heap (k-way merge)
Order doesn't matter → just concatenate and sort

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Two Sorted Lists
Coming soon
Same merge logic on linked lists — splice nodes instead of writing array slots.
Merge k Sorted Lists
Coming soon
Generalises to k inputs — use a min-heap of the current heads, O(N log k).
Squares of a Sorted Array
Two pointers from both ends, fill the output from the back with the larger square.
Sort Colors
Coming soon
In-place partitioning with pointers — another O(1)-space array rearrangement.

Same pattern

←

Trapping Rain Water

Continue · Next problem

Remove Duplicates from Sorted Array