Merge Sorted Array easy

Problem Statement

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

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]

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1]

Steps

1. Initialize Pointers: Use three pointers: p1 to iterate through nums1 (from the end, initially pointing to m-1), p2 to iterate through nums2 (from the end, initially pointing to n-1), and p to iterate through the merged array (also from the end, initially pointing to m+n-1).

2. Compare and Place: Compare the elements at nums1[p1] and nums2[p2]. The larger element is placed at nums1[p]. Decrement the pointer of the larger element and p.

3. Handle Remaining Elements: If one of the arrays is exhausted (p1 or p2 becomes negative), copy the remaining elements of the other array into nums1.

Explanation

The algorithm efficiently merges the two sorted arrays by comparing elements from the end. This avoids the need for shifting elements multiple times. It works because we're placing the largest elements first, at the end of the merged array. Then, as we move towards the beginning, we are filling in the gaps with the next largest element. This ensures the final merged array is sorted in ascending order.

Code

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1; // Pointer for nums1
        int p2 = n - 1; // Pointer for nums2
        int p = m + n - 1; // Pointer for merged array (nums1)

        // Compare elements from the end and place the larger one in nums1
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }

        // Copy remaining elements from nums2 if any
        while (p2 >= 0) {
            nums1[p] = nums2[p2];
            p2--;
            p--;
        }
    }
}

Complexity

• Time Complexity: O(m + n). We iterate through both arrays once.
• Space Complexity: O(1). We use only a few constant extra variables. The merging happens in-place within nums1.