Description

You are given two sorted arrays:

• nums1 contains m valid elements followed by n empty spaces (0s).
• nums2 contains n sorted elements.

Your task is to merge nums2 into nums1 so that nums1 becomes one sorted array.

The important catch is that you must modify nums1 in-place. You cannot return a new 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]

My Solution

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:

        i, j, last = m - 1, n - 1, m + n - 1

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

        while j >= 0:
            nums1[last] = nums2[j]
            j -= 1
            last -= 1

Intuition

The obvious solution would be:

1. Copy every element from nums2 into the empty spaces of nums1.
2. Sort the entire array.

Although this works, sorting costs O((m+n) log(m+n)).

Since both arrays are already sorted, we should be able to do much better.

The challenge is that we're writing directly into nums1.

If we started merging from the beginning, we'd overwrite values in nums1 that we haven't compared yet.

Instead, we work backwards.

The Key Insight

The extra space in nums1 is already at the end.

nums1
[1,2,3,0,0,0]
       ^^^^^^
    free space

The largest value among both arrays always belongs at the very end.

So instead of filling from left to right, we fill from right to left.

This means we never overwrite useful values.

Three Pointers

We maintain three pointers:

i    -> last valid element in nums1
j    -> last element in nums2
last -> final insertion position

Initially,

nums1 = [1,2,3,0,0,0]
               i     last

nums2 = [2,5,6]
             j

i = m - 1
j = n - 1
last = m + n - 1

Step 1

Compare:

nums1[i] = 3
nums2[j] = 6

Since 6 is larger,

[1,2,3,0,0,6]

Move:

j--
last--

Step 2

Compare

3 vs 5

5 is larger.

[1,2,3,0,5,6]

Move pointers.

Step 3

Compare

3 vs 2

3 is larger.

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

Move i.

Continue

Eventually,

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

Everything ends up in the correct position without ever needing an additional array.

Why We Merge From the End

Suppose we tried writing from the front.

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

After writing one element, we'd overwrite values in nums1 that we still need to compare later.

Working backwards avoids this completely because the empty slots are already at the end.

Why Do We Need the Second While Loop?

Our main loop stops when either array is exhausted.

while i >= 0 and j >= 0:

There are two possibilities.

Case 1

nums2 finishes first.

Example:

nums1 = [4,5,6]
nums2 = [1,2,3]

After merging,

[1,2,3,4,5,6]

The remaining elements already in nums1 are already in the correct place.

Nothing else needs to be done.

Case 2

nums1 finishes first.

Example:

nums1 = [1]
nums2 = [2,3,4]

After the first loop,

[1,2,3,4]

There are still values left in nums2 that haven't been copied.

That's why we need:

while j >= 0:
    nums1[last] = nums2[j]
    j -= 1
    last -= 1

Notice there is no corresponding loop for nums1.

Any remaining values from nums1 are already exactly where they belong.

Edge Cases

Empty nums2

nums1 = [1]
nums2 = []

Nothing changes.

Empty nums1

nums1 = [0]
nums2 = [1]

The second loop copies everything from nums2.

Result:

[1]

Duplicate Values

nums1 = [2,2,4]
nums2 = [2,3]

The algorithm naturally handles duplicates since it always picks the larger element from the end.

Complexity Analysis

Time Complexity

Each pointer only moves in one direction.

Every element is processed at most once.

Time: O(m + n)

Space Complexity

Only three integer pointers are used.

No extra arrays are created.

Space: O(1)

Key Takeaways

• Since both arrays are already sorted, sorting again is unnecessary.
• The empty space at the end of nums1 makes it possible to merge in-place.
• Filling the array from right to left prevents overwriting values that still need to be compared.
• The algorithm only requires three pointers and runs in linear time.
• If nums2 has remaining elements after the main loop, they must be copied over. Remaining elements in nums1 are already in the correct position and require no additional work.