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 greater or 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: Create three pointers: p1 pointing to the end of nums1 (index m-1), p2 pointing to the end of nums2 (index n-1), and p pointing to the end of the merged array (index m+n-1).

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

3. Handle Remaining Elements: One of the arrays will be exhausted first. Copy the remaining elements from the non-exhausted array to the beginning of nums1.

Explanation:

The algorithm works by iteratively comparing the largest elements from both sorted arrays. Because we are working from the end of each array, we can directly place the larger element into its correct sorted position in nums1 without needing to shift other elements. This avoids the need for multiple passes and results in a single-pass, efficient solution.

Code:

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let p1 = m - 1;
    let p2 = n - 1;
    let 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--;
    }

    // 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 a constant amount of extra space for the pointers. The space used by the input arrays is not considered in space complexity analysis.