Leetcode problem 71 - 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 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.

/**
 * @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) {
  // Initialize pointers for the merged array (nums1)
  let i = m - 1; // Pointer for the last element in nums1
  let j = n - 1; // Pointer for the last element in nums2
  let k = m + n - 1; // Pointer for the last position in the merged array (nums1)

  // Iterate through nums2 from the end to the beginning
  while (j >= 0) {
    // If there are elements remaining in nums1 and the current element in nums1 is greater
    if (i >= 0 && nums1[i] > nums2[j]) {
      // Copy the greater element from nums1 to the end of the merged array
      nums1[k--] = nums1[i--];
    } else {
      // Copy the current element from nums2 to the end of the merged array
      nums1[k--] = nums2[j--];
    }
  }
};

Starting from the end of each array, the algorithm compares elements and places them in descending order in nums1. The while loop iterates through nums2, and the time complexity is O(m + n), where m and n are the lengths of nums1 and nums2, respectively. The algorithm efficiently combines the arrays by avoiding the need for additional space and achieving a linear time complexity relative to the total number of elements in the input arrays.