Merge Sorted Array

Try It Yourself

Use the editor below to merge nums2 into the available space at the end of nums1. Compare the largest remaining values so unread values in nums1 are not overwritten.

Submit your implementation when it passes the examples. Either input range may be empty, and values may be negative.

Merge Sorted Array

easySorting · Two Pointers25 minLC 88

Problem

nums1 contains m sorted values followed by enough zero placeholders to hold nums2. nums2 contains n sorted values.

Merge nums2 into nums1 in non-decreasing order and return nums1.

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]

Example 2:

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

Output: [1]

Constraints

nums1.length = m + n
Both input ranges are sorted.

0 attempts

Solution

Start three pointers at the last real value of nums1, the last value of nums2, and the last available position. Write the larger candidate into the open position and move its pointer backward.

When nums2 is exhausted, every remaining nums1 value is already correctly placed.

function mergeSortedArray(nums1, m, nums2, n) {
  let first = m - 1;
  let second = n - 1;
  let write = m + n - 1;

  while (second >= 0) {
    if (first >= 0 && nums1[first] > nums2[second]) {
      nums1[write] = nums1[first];
      first--;
    } else {
      nums1[write] = nums2[second];
      second--;
    }

    write--;
  }

  return nums1;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(m + n)`	Each value from the two sorted ranges is considered at most once.
Auxiliary space	`O(1)`	The merge writes into nums1's existing storage.