[LeetCode 88] Merge Sorted Array: Why Working Backwards is Faster?

Hi everyone! 👋 Today I want to share a classic LeetCode problem that recently gave me a great "Aha!" moment: Merge Sorted Array (LeetCode 88).

At first glance, this looks like a simple Easy problem. However, solving it in-place (without extra memory) and optimizing it for performance requires a bit of "reverse" thinking. Let's dive in!

1. The Problem

You are given two integer arrays nums1 and nums2, both sorted in non-decreasing order.

• nums1 has a size of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 (placeholders for nums2).

• nums2 has n elements.

Task: Merge nums2 into nums1 as one sorted array. You must modify nums1 in-place.

Example:

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

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

2. Common Approaches

Approach 1: The "Naive" Way (Merge and Sort)

The simplest solution: just append nums2 to the end of nums1, then call the built-in sort function.

// JS
nums1.splice(m, n, ...nums2);
nums1.sort((a, b) => a - b);

• Time Complexity: $O((m+n) \log(m+n))$ due to the sorting cost.

• Verdict: Too slow. We aren't taking advantage of the fact that the two arrays are already sorted.

Approach 2: Two Pointers (Forward)

Use two pointers, p1 and p2, starting at the beginning of each array. You would typically create a copy of nums1 or a new result array to store the merged output, then copy it back.

• Time Complexity: $O(m+n)$. Good!

• Space Complexity: $O(m)$. Not ideal because the problem asks for an in-place solution.

3. The Optimal Solution: Two Pointers (Backward) 🚀

If we iterate from the start (index 0), inserting an element from nums2 into nums1 would force us to shift all subsequent elements to the right. This is very expensive.

The Idea: Since nums1 has empty space (zeros) at the end, why don't we start filling it from right to left?
The largest number between the two arrays is guaranteed to end up at the very last position. We simply compare the tail of nums1 with the tail of nums2 and place the larger one at the end.

The Algorithm:

1. p1 points to the last valid element of nums1 (index m-1).

2. p2 points to the last element of nums2 (index n-1).

3. p points to the last position of the nums1 array (index m+n-1).

4. Compare nums1[p1] and nums2[p2]. Place the larger value at nums1[p].

The Gotcha ⚠️

A common bug is forgetting the edge case where nums1 runs out of elements (p1 < 0) but nums2 still has elements left.
Example: nums1 = [4,5,6,0,0,0], nums2 = [1,2,3].
After placing 4, 5, and 6 at the end, nums1 is exhausted. We must continue to copy the remaining elements of nums2 ([1,2,3]) into the front of nums1.

Implementation (JavaScript):

var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    let p = (m + n) - 1;

    // We only care while nums2 still has elements
    while (p2 >= 0) {
        // If p1 is valid AND nums1[p1] is greater than nums2[p2]
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            // Otherwise (including when p1 is exhausted < 0)
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
};

4. Visualizing the Logic 🎨

5. Complexity Analysis

• Time Complexity: $O(m + n)$. We iterate through each element exactly once.

• Space Complexity: $O(1)$. We modify nums1 directly without using extra data structures.

6. Conclusion

This problem taught me an important lesson in array manipulation: When inserting from the front is costly (due to shifting), try thinking backwards from the end.

Hope this post helps you on your coding journey! If you found it useful, give it a like ❤️.

#LeetCode #Algorithms #JavaScript #Python #Programming