leetcode-150

1. Merge Sorted Array

Problem Statement

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
  • -109 <= nums1[i], nums2[j] <= 109

 

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

Solution

Merging Two Sorted Arrays In-Place

Problem Statement:

We are given two sorted integer arrays, nums1 and nums2, along with two integers, m and n, representing the number of elements in each respective array. The task is to merge nums2 into nums1 in sorted order, modifying nums1 in-place. nums1 has enough space (m + n length) to accommodate all elements.

Constraints:

Algorithm Explanation:

To efficiently merge the arrays in-place, we utilize a three-pointer approach starting from the back:

  1. Initialize Three Pointers:
    • i = m - 1 (Last valid element in nums1)
    • j = n - 1 (Last element in nums2)
    • k = m + n - 1 (Last position in nums1 to fill)
  2. Merge Elements from the End:
    • Compare nums1[i] and nums2[j].
    • Place the larger element at nums1[k].
    • Decrement the respective pointer and k.
  3. Handle Remaining Elements in nums2:
    • If nums2 has leftover elements, copy them to nums1.
    • No need to copy nums1’s remaining elements since they are already in place.
  4. Time Complexity:
    • O(m + n) as each element is processed once.
    • O(1) space since it is done in-place.

Implementation:

function merge(nums1, m, nums2, n) {
    let i = m - 1; // Last index of nums1's actual elements
    let j = n - 1; // Last index of nums2
    let k = m + n - 1; // Last index of nums1 (full size)

    // Merge from the back
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }

    // If nums2 still has elements left, copy them
    while (j >= 0) {
        nums1[k] = nums2[j];
        j--;
        k--;
    }
}

This ensures an optimal in-place merge without extra space. 🚀

Leetcode Reference: 88. Merge Sorted Array

Previous Next
This site is open source. Improve this page.