LeetCode 88 – Merge Sorted Array

Merge Sorted Array is tagged Easy and has one idea in it that is worth more than most Mediums: when writing into an array you are also reading, go backwards. That single move turns a problem that seems to need a scratch buffer into a clean in-place merge, and the same trick shows up any time output and input share memory.

The problem

nums1 has length m + n: the first m slots hold sorted values and the last n are zeros, reserved as space. nums2 holds n sorted values. Merge nums2 into nums1 in place, keeping it sorted. Return nothing.

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

nums1 = [1], m = 1, nums2 = [], n = 0   -> [1]
nums1 = [0], m = 0, nums2 = [1], n = 1  -> [1]     nums1 contributes nothing
nums1 = [4,5,6,0,0,0], m = 3
nums2 = [1,2,3], n = 3            -> [1,2,3,4,5,6] every nums2 value comes first

The trailing zeros are not data. They are the problem telling you the answer is meant to fit where it already is.

Why forwards fails

The textbook merge walks both inputs from the front, taking the smaller each time. Try it here and the first write destroys something you still need:

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

write position 0: min(4, 1) = 1, from nums2
                  [1,5,6,0,0,0]
                   ^
                   the 4 is GONE, and it was never consumed

The write pointer is always at or ahead of the nums1 read pointer, so it eventually lands on unread data. The usual fix is a scratch copy of nums1's first m values — correct, O(m) extra space, and it works. Say it, then improve it.

Backwards, and the space disappears

Fill from the largest value down, writing into the empty tail. Now the write pointer starts at the very end and the read pointers start at m - 1 and n - 1, so the write position is always strictly ahead of both:

nums1 = [1,2,3,_,_,_]        nums2 = [2,5,6]
             i     w                      j

3 vs 6 -> take 6   [1,2,3,_,_,6]
3 vs 5 -> take 5   [1,2,3,_,5,6]
3 vs 2 -> take 3   [1,2,3,3,5,6]   writes onto the 3 it just consumed -- safe
2 vs 2 -> take 2   [1,2,2,3,5,6]   nums2 exhausted; the leading 1 is already home

The invariant to state out loud: the number of slots remaining to write always equals the number of values remaining to place, so the write pointer can never overtake a read pointer. Overwriting a slot you already consumed is fine; that is the case in step three above.

Loop on nums2 only

The second trick halves the code. When nums2 is exhausted, everything left in nums1 is already sorted and already in the right place, so there is nothing to do. When nums1 is exhausted, the remaining nums2 values still have to be copied in. The two are not symmetric, so loop while j >= 0 and let i run out naturally.

Java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;              // last real value in nums1
        int j = n - 1;              // last value in nums2
        int write = m + n - 1;      // last slot overall

        // Only j matters: when nums2 runs out, nums1's remainder is already placed.
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[write--] = nums1[i--];
            } else {
                nums1[write--] = nums2[j--];
            }
        }
    }
}

i >= 0 && comes first so that a negative index is never dereferenced — short-circuiting is load-bearing, not stylistic. When i falls below zero the condition is false and every remaining value is taken from nums2, which is exactly right.

nums1[i] > nums2[j] with a strict > means ties take from nums2 first. Either choice produces a correctly sorted array here since the values are plain integers, but on records sorted by a key it is the difference between a stable merge and an unstable one — worth one sentence, and worth knowing which way you chose.

Python

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        i, j, write = m - 1, n - 1, 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

Two Python-specific traps here. The function must mutate nums1 and return None — nums1 = sorted(nums1[:m] + nums2) rebinds a local name and the caller sees nothing at all. And i >= 0 is not optional decoration: nums1[-1] is the last element rather than an error, so dropping the guard reads real data from the wrong end and returns a plausible wrong answer instead of raising.

nums1[:] = sorted(nums1[:m] + nums2) does mutate in place and is genuinely correct — mention it, note that it is O((m+n) log(m+n)) and allocates, and then write the linear merge.

Complexity

Each value is written exactly once and read exactly once. Sorting throws away the fact that both inputs are already sorted, which is the information the problem handed you — reaching for a sort here is the thing being tested against.

The pattern

Writing backwards to avoid a temporary buffer generalises well. It is the merge step of merge sort with the buffer removed, it is how you shift an array right in place, and it is the standard answer to Squares of a Sorted Array (977), where the largest values sit at the two ends and filling from the back means never needing scratch space.

The general rule: when the output overlaps the input, fill from whichever end the output does not yet occupy.

What the interviewer is checking

• That you spot the trailing zeros as reserved space, not data.
• That you explain why forwards clobbers unread values before offering backwards.
• That the loop condition is on j, and why i running out is harmless.
• i >= 0 guarding the dereference — and in Python that a negative index silently wraps.
• m = 0 and n = 0.
• That the function mutates rather than returns, especially in Python.
• Tie-breaking, and whether the merge is stable.