24. Merge Sorted Array

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. Merge nums2 into nums1 as one sorted array. nums1 has enough space (length m + n) to hold additional elements from nums2.

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

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

Problem Breakdown:

1. Use three pointers: p1 at the end of nums1's real elements (m-1), p2 at the end of nums2 (n-1), and p at the end of nums1's total space (m+n-1).

• p1 = m - 1
  p2 = n - 1
  p = m + n - 1

2. Work backwards, placing the larger element at position p. This avoids overwriting elements we haven't processed yet.

• while p1 >= 0 and p2 >= 0:
      if nums1[p1] > nums2[p2]:
          nums1[p] = nums1[p1]
          p1 -= 1
      else:
          nums1[p] = nums2[p2]
          p2 -= 1
      p -= 1

3. If nums2 has remaining elements, copy them over. If nums1 has remaining elements, they are already in place.

• while p2 >= 0:
      nums1[p] = nums2[p2]
      p2 -= 1
      p -= 1

Summary:

Merge from the back to avoid overwriting. Use three pointers starting at the ends. Compare elements from both arrays, placing the larger one at the back of nums1. Handle remaining nums2 elements.

Time and Space Complexity:

Time Complexity: O(n + m) - we process each element once.

Space Complexity: O(1) - we merge in-place.

Python Solution:

def merge(nums1, m, nums2, n):
    p1, p2, p = m - 1, n - 1, m + n - 1
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

JavaScript Solution:

var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1, p2 = n - 1, p = m + n - 1;
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p--] = nums1[p1--];
        } else {
            nums1[p--] = nums2[p2--];
        }
    }
    while (p2 >= 0) {
        nums1[p--] = nums2[p2--];
    }
};

Java Solution:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1, p = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p--] = nums1[p1--];
            } else {
                nums1[p--] = nums2[p2--];
            }
        }
        while (p2 >= 0) {
            nums1[p--] = nums2[p2--];
        }
    }
}