88. Merge Sorted Array

Problem Statement

You are given two integer arrays, nums1 and nums2, sorted in non-decreasing order, and two integers m and n representing the number of initialized elements in each. The goal is to merge nums2 into nums1 as a single sorted array. The final result must be stored in nums1, which has a length of m + n to accommodate the merged elements.

Optimal Approach: Work Backwards

A naive solution starting from the beginning of the arrays is inefficient because inserting an element from nums2 into nums1 would require shifting all subsequent elements of nums1. This can lead to a time complexity of $O(m \times n)$.

The optimal solution avoids this by populating nums1 from the end to the beginning. This utilizes the empty space at the end of nums1 and prevents overwriting data that still needs to be processed.

This approach uses three pointers:

1. p1: Points to the last initialized 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 nums1 (index m + n - 1), serving as the write-pointer.

The algorithm proceeds as follows:

• While there are still elements to consider in nums2 (p2 >= 0), compare the values at nums1[p1] and nums2[p2].
• Place the larger of the two values at nums1[p].
• Decrement the pointer (p1 or p2) corresponding to the array from which the element was taken.
• Decrement the write-pointer p.

If p1 becomes negative, it means all remaining elements from nums2 are smaller than any element in the initial nums1 array, so they are simply copied over. If p2 becomes negative first, the remaining elements in nums1 are already in their correct sorted positions, and no further action is needed.

---

Implementation

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // Pointer for the last element of the initial nums1
    let p1 = m - 1;
    // Pointer for the last element of nums2
    let p2 = n - 1;
    // Pointer for the last spot in the merged nums1 array
    let p = m + n - 1;
 
    // Loop backwards as long as there are elements in nums2
    while (p2 >= 0) {
        // If p1 is valid and its value is greater, use the nums1 element
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            // Otherwise, use the nums2 element
            nums1[p] = nums2[p2];
            p2--;
        }
        // Move the write pointer to the left
        p--;
    }
};

---

Complexity Analysis

• Time Complexity: O(m + n). Every element from both arrays is read and written exactly once.
• Space Complexity: O(1). The merge operation is performed in-place, using only a constant amount of extra space for the pointers.

---