LeetCode 88: Merge Sorted Array

A detailed guide to solving Merge Sorted Array in-place by merging from the back with three pointers.

leetcodearraytwo-pointerssorting

Problem Restatement

We are given two integer arrays:

nums1
nums2

Both arrays are sorted in non-decreasing order.

We are also given two integers:

m
n

The first m elements of nums1 are valid sorted elements.

The array nums2 contains n valid sorted elements.

The total length of nums1 is m + n, so it has enough space to hold all elements from both arrays.

We need to merge nums2 into nums1 in-place, so that nums1 becomes one sorted array.

The function should not return the final array. It should modify nums1 directly. The last n zeroes in nums1 are placeholders and should be ignored before merging.

Input and Output

Item Meaning
Input nums1, m, nums2, n
Output Nothing returned
Mutation Store the merged sorted result inside nums1
Valid part of nums1 First m elements
Valid part of nums2 All n elements
Placeholder part Last n elements of nums1

Function shape:

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

Examples

Example 1:

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

The valid arrays are:

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

After merging:

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

Example 2:

nums1 = [1]
m = 1
nums2 = []
n = 0

There is nothing to merge from nums2.

After merging:

nums1 = [1]

Example 3:

nums1 = [0]
m = 0
nums2 = [1]
n = 1

There are no valid elements in nums1.

The 0 is only placeholder space.

After merging:

nums1 = [1]

First Thought: Use an Extra Array

A simple way is to copy the valid part of nums1 and all of nums2 into a new array, sort it, then copy it back.

merged = nums1[:m] + nums2
merged.sort()
nums1[:] = merged

This works, but it does not use the sorted structure fully.

It also uses extra space.

We can do better by merging directly.

Key Insight

Both arrays are already sorted.

If we merge from the front, we may overwrite valid elements in nums1.

Example:

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

If we place 2 from nums2 near the front, we may overwrite 2 or 3 from the valid part of nums1.

But nums1 has empty space at the back.

So we merge from the back.

The largest remaining value among both arrays belongs at the last open position in nums1.

Use three pointers:

Pointer Starts at Meaning
i m - 1 Last valid element in nums1
j n - 1 Last element in nums2
write m + n - 1 Position to fill next in nums1

At every step, compare:

nums1[i]
nums2[j]

Place the larger one at:

nums1[write]

Then move the corresponding pointer left.

Algorithm

Initialize:

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

While j >= 0:

  1. If i >= 0 and nums1[i] > nums2[j], place nums1[i] at nums1[write].
  2. Otherwise, place nums2[j] at nums1[write].
  3. Move the pointer that supplied the value.
  4. Move write left.

We only need to loop while j >= 0.

If nums2 is fully copied, the remaining valid elements of nums1 are already in the correct place.

Walkthrough

Use:

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

Start:

i = 2       # nums1[i] = 3
j = 2       # nums2[j] = 6
write = 5

Compare 3 and 6.

Place 6 at the end:

nums1 = [1, 2, 3, 0, 0, 6]
j = 1
write = 4

Compare 3 and 5.

Place 5:

nums1 = [1, 2, 3, 0, 5, 6]
j = 0
write = 3

Compare 3 and 2.

Place 3:

nums1 = [1, 2, 3, 3, 5, 6]
i = 1
write = 2

Compare 2 and 2.

Since nums1[i] > nums2[j] is false, place nums2[j]:

nums1 = [1, 2, 2, 3, 5, 6]
j = -1
write = 1

Now nums2 is fully copied.

Stop.

The final array is:

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

Correctness

The algorithm fills nums1 from right to left.

At each step, write points to the largest still-empty position in the final merged array.

The largest remaining value must be either the last unused valid value of nums1 or the last unused value of nums2, because both arrays are sorted.

So comparing nums1[i] and nums2[j] identifies the correct value for nums1[write].

After placing that value, the algorithm moves the corresponding pointer left. The suffix after write is now correct and will never be changed again.

This invariant holds after every step: all positions to the right of write contain the largest already-merged values in sorted order.

When nums2 has no remaining elements, every value from nums2 has been placed. Any remaining values from the original valid part of nums1 are already before write and already sorted. Therefore, the whole array is correctly merged.

Complexity

Let:

m = number of valid elements in nums1
n = number of elements in nums2
Metric Value Why
Time O(m + n) Each element is considered at most once
Space O(1) The merge uses only three pointers

Implementation

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        i = m - 1
        j = n - 1
        write = m + n - 1

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

            write -= 1

Code Explanation

Start at the end of the valid part of nums1:

i = m - 1

Start at the end of nums2:

j = n - 1

Start writing at the final position of nums1:

write = m + n - 1

The loop continues until all values from nums2 are placed:

while j >= 0:

If nums1 still has values and its current value is larger, use it:

if i >= 0 and nums1[i] > nums2[j]:
    nums1[write] = nums1[i]
    i -= 1

Otherwise, use the current value from nums2:

else:
    nums1[write] = nums2[j]
    j -= 1

Then move the write pointer left:

write -= 1

No return statement is needed because LeetCode checks the mutation of nums1.

Testing

def check(nums1, m, nums2, n, expected):
    s = Solution()
    s.merge(nums1, m, nums2, n)
    assert nums1 == expected

def run_tests():
    check([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3, [1, 2, 2, 3, 5, 6])
    check([1], 1, [], 0, [1])
    check([0], 0, [1], 1, [1])
    check([2, 0], 1, [1], 1, [1, 2])
    check([1, 2, 4, 0, 0, 0], 3, [2, 3, 5], 3, [1, 2, 2, 3, 4, 5])
    check([-1, 0, 0, 3, 3, 3, 0, 0, 0], 6, [1, 2, 2], 3, [-1, 0, 0, 1, 2, 2, 3, 3, 3])

    print("all tests passed")

run_tests()

Test meaning:

Test Why
[1, 2, 3] and [2, 5, 6] Main example
nums2 empty Nothing to merge
nums1 has no valid elements Copy all of nums2
Smaller nums2 element Confirms backward merge can overwrite placeholder correctly
Interleaved arrays Checks normal merge behavior
Negative numbers and duplicates Confirms sorted order with repeated values