88. Merge Sorted Array

Description

Difficulty: Easy

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10⁹ <= nums1[i], nums2[j] <= 10⁹

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Solution

A key constraint is that nums1 has enough space to accommodate all elements from both arrays (specifically, its initial size is m + n, where m is the number of actual elements in nums1 and n is the number of elements in nums2). The operation is performed in-place, directly modifying nums1 without using additional auxiliary arrays for the primary merge logic.

The strategy employs a three-pointer approach, working from the end of the arrays towards the beginning to avoid overwriting elements in nums1 that have not yet been moved.

1. Pointer Initialization:

   • p1: Initialized to m - 1, pointing to the last valid element in nums1 (before any elements from nums2 are considered).

   • p2: Initialized to n - 1, pointing to the last element in nums2.

   • p: Initialized to m + n - 1, pointing to the last available position in nums1 where merged elements will be placed.

2. Main Merge Loop (while (p1 >= 0 && p2 >= 0)): This loop continues as long as there are elements remaining in both nums1 (original part) and nums2 to compare.

   • Comparison: At each step, the elements nums1[p1] and nums2[p2] are compared.

   • Placement:

     • If nums1[p1] is greater than or equal to nums2[p2], it signifies that nums1[p1] is the largest among the currently considered elements. Thus, nums1[p1] is moved to nums1[p]. p1 is then decremented to consider the next smaller element in nums1.

     • Otherwise (if nums2[p2] is larger), nums2[p2] is moved to nums1[p]. p2 is then decremented to consider the next smaller element in nums2.

   • Destination Pointer Decrement: In either case, p is decremented as an element has been placed in its final sorted position in nums1.

3. Handling Remaining Elements (while (p2 >= 0)): After the main loop finishes, it's possible that elements from nums2 still remain (if all elements from nums1 were smaller and exhausted first).

   • This loop copies any remaining elements from nums2 directly into the beginning of nums1 (which would be the available slots pointed to by p). Both p2 and p are decremented in each iteration until all elements from nums2 are moved. (Note: No similar loop is needed for nums1 because its remaining elements would already be in their correct sorted positions at the beginning of nums1 if p2 became -1 first.)

Code

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;

        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] >= nums2[p2]) {
                nums1[p] = nums1[p1];
                --p1;
            } else {
                nums1[p] = nums2[p2];
                --p2;
            }
            --p;
        }

        while (p2 >= 0) {
            nums1[p] = nums2[p2];
            --p2;
            --p;
        }

    }
}

Time Complexity: O(m + n)
The algorithm performs a single pass, in reverse, through both arrays. In the worst case, each element from nums1 (m elements) and nums2 (n elements) is visited and moved exactly once. Therefore, the number of operations is directly proportional to the total number of elements being merged.

Space Complexity: O(1)
The algorithm operates entirely in-place, modifying nums1 directly. It uses only a few constant-space pointers (p1, p2, p), regardless of the input array sizes. No auxiliary data structures that scale with m or n are allocated.