Merge Sorted Array Easy 0 attempts
LeetCode ↗

Merge Sorted Array

Easy ArrayTwo Pointers LeetCode

You're given two arrays, nums1 and nums2, both already sorted in non-decreasing order, along with integers m and n telling you how many actual elements each array holds. The first m entries of nums1 are valid data, followed by n reserved slots; all n entries of nums2 are valid. Combine them into one sorted array, writing the result directly back into nums1 rather than returning a new array.

Input Format
Implement merge(nums1, m, nums2, n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Modify argument 1 in place. The editor compares its final value; the function return value is ignored.

Sample Input and Output

Example 1 ยท Run Sample

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 = [0]
m = 0
nums2 = [1]
n = 1
Output
[1]
Constraints
  • nums1.length == m + n; nums2.length == n
  • 0 <= m, n <= 200; m + n >= 1
  • Valid portions of both arrays are sorted in non-decreasing order.
  • -10^9 <= nums1[i], nums2[j] <= 10^9
Test Cases (2)
Case 1
Args: [[1,2,3,0,0,0],3,[2,5,6],3] Expected: [1,2,2,3,5,6]
Case 2
Args: [[0],0,[1],1] Expected: [1]
Topics
ArrayTwo Pointers

Use three pointers starting from the end of both arrays and the end of nums1. Fill nums1 from the back by comparing elements, which avoids overwriting elements that still need to be processed.

javascript
function merge(nums1, m, nums2, n) {
  let i = m - 1, j = n - 1, k = m + n - 1;

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

  while (j >= 0) {
    nums1[k--] = nums2[j--];
  }
}

Time: O(m + n) Space: O(1)

Saved in this browser only. Private to you.

JavaScript