Merge Sorted Array Easy 0 attempts
LeetCode ↗

Merge Sorted Array

Easy ArrayTwo Pointers LeetCode

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 in-place within nums1.

Sample Input
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Sample Output
[1,2,2,3,5,6]
Constraints
  • m + n == nums1.length
  • 0 <= m, n <= 200
  • -10^9 <= nums1[i], nums2[j] <= 10^9
Test Cases
Case 1
Args: [[1,2,3,0,0,0],3,[2,5,6],3] Expected: [1,2,2,3,5,6]
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.

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