88. Merge Sorted Array (In-Place)¶

Question¶

You are given two integer arrays \(nums1\) and \(nums2\), sorted in non-decreasing order. You are also given integers \(m\) and \(n\), which represent the number of initialized elements in \(nums1\) and \(nums2\) respectively.

Merge \(nums1\) and \(nums2\) into a single array sorted in non-decreasing order. The final sorted array must be stored in-place inside the array \(nums1\). To accommodate this, \(nums1\) has a total length of \(m + n\).

Solution¶

Pattern¶

Backward Three-Pointer Manipulation Instead of processing elements from the beginning (which forces an expensive array shift operation), compare and write elements starting from the back of the pre-allocated buffer space.

How to Identify¶

Two input data structures are provided already sorted.
The destination container contains trailing empty padding explicitly designed to fit the incoming dataset.
Constraints demand an in-place modification with \(O(1)\) auxiliary space.

Description¶

Step-by-step explanation:

Step 1: Pointer Initialization. Create three tracking pointers:
- p1 positioned at the end of valid data in \(nums1\) (\(m - 1\)).
- p2 positioned at the end of \(nums2\) (\(n - 1\)).
- w (write pointer) positioned at the absolute end of the \(nums1\) storage buffer (\(m + n - 1\)).
Step 2: Core Processing Loop. Execute a loop that runs continuously as long as there are valid uncopied elements remaining in \(nums2\) (\(p2 \ge 0\)).
Step 3: Evaluation & Assignment. - If p1 >= 0 and \(nums1[p1] > nums2[p2]\), copy the value at \(nums1[p1]\) to \(nums1[w]\), then decrement p1.
- Otherwise, copy the value at \(nums2[p2]\) to \(nums1[w]\), then decrement p2.
Step 4: Shift Write Position. Decrement the write pointer w after every assignment step.
Step 5: Implicit Completion. Once p2 drops below 0, terminate. Any remaining elements belonging to \(nums1\) are already left in their correctly sorted configurations.

The Intuition¶

Think of this as loading a delivery truck from back to front.

If you try to load new packages into the front of the truck (\(nums1\)), you would have to manually push all the existing items (\(m\) elements) backward every single time to clear out space, resulting in highly inefficient work.

By starting at the very back of the truck where empty space is guaranteed (\(m + n - 1\)), you can compare the largest items from both sets and place them securely in position. You never have to shift any items, and you will never accidentally crush (overwrite) a package that hasn't been scanned yet.

Complexity¶

Label	Worst	Average
Time Complexity	\(O(m + n)\)	\(O(m + n)\)
Space Complexity	\(O(1)\)	\(O(1)\)

Time Complexity¶

\(O(m + n)\). In the worst-case scenario, every item from both inputs must be individually evaluated and written into the composite layout. Each element is moved at most once.

Space Complexity¶

\(O(1)\). The solution edits elements completely in-place inside the pre-allocated tail space of \(nums1\). No dynamic tracking collections or recursive stack contexts are used.

Code¶

class Solution {
    /**
     * Merges nums2 into nums1 backwards to guarantee O(1) auxiliary space.
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Isolate pointers to avoid destroying the input method parameters
        int p1 = m - 1;        // High index of valid data in nums1
        int p2 = n - 1;        // High index of data in nums2
        int w = m + n - 1;     // Global write pointer at the back of the buffer

        // The process is complete the exact moment nums2 elements are exhausted.
        // If nums1 empties out early, the conditional block naturally flushes nums2 items forward.
        while (p2 >= 0) {
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[w] = nums1[p1];
                p1--;
            } else {
                nums1[w] = nums2[p2];
                p2--;
            }
            w--; // Pull the global write tracking position backward
        }
    }
}

Caveats¶

Short-Circuit Order Check: The index out-of-bounds guard p1 >= 0 must be written prior to evaluating nums1[p1] in the conditional check expression. Reversing this order will cause a runtime exception if \(nums1\) runs out of elements first.
The Early Termination Trap: Do not write the loop boundary condition as while (p1 >= 0 && p2 >= 0). If you do, the loop will exit early if \(nums1\) elements are exhausted first, leaving the remaining smaller items of \(nums2\) completely missing from the front of the array.

Concepts to Think About¶

Stable Sort Consistency: Utilizing a strict inequality check (> instead of >=) ensures that the relative placement order of identical matching keys coming from different source streams remains stable.
Hardware Cache Layouts: Iterating through sequential memory arrays from back to front reads contiguous cash blocks, which plays favorably with modern hardware architecture pre-fetching rules.
System Buffer Architecture: This strategy mirrors lower-level operating system network ring-buffer mechanics, where structural padding spaces are pre-allocated to bypass secondary allocation bottlenecks.

Logical Follow-up¶

Question: How would you resolve this problem if \(nums1\) did not possess any trailing buffer padding?

Solution: To maintain \(O(1)\) space without padding, you would be forced to insert from the front and shift elements downstream on insertions, degrading runtime performance to \(O(m \cdot n)\). To maintain linear \(O(m + n)\) time, you would have to allocate an auxiliary data array copy of size \(m\), moving your auxiliary space footprint up to \(O(m)\).

Question: How does the strategy shift if the input datasets are presented as two Singly Linked Lists instead of sequential memory arrays?

Solution: Linked lists allow structural modification via pointer manipulation without memory shifting overhead. A forward merge pattern is preferred here: you maintain a dummy head node and stitch the pointers together from smallest to largest. The time complexity stays \(O(m + n)\), and the space complexity stays \(O(1)\).