LeetCode 88: Merge Sorted Array

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

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:

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

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: