Merge Sorted Arrays

Problem Statement

You are given two sorted arrays nums1 and nums2. Merge nums2 into nums1 as one sorted array, modifying nums1 in-place.

nums1 has enough space at the end to hold all elements from nums2. The parameter m represents the number of valid elements in nums1, and n represents the number of elements in nums2.

Function Signature:

function merge(nums1, m, nums2, n) {
  // Your code here
}

Examples

nums1	m	nums2	n	Result
[1, 2, 3, 0, 0, 0]	3	[2, 5, 6]	3	[1, 2, 2, 3, 5, 6]
[1]	1	[]	0	[1]
[0]	0	[1]	1	[1]

Constraints

• nums1.length = m + n
• nums2.length = n
• 0 ≤ m, n ≤ 200
• -10⁹ ≤ nums1[i], nums2[j] ≤ 10⁹
• Both arrays are sorted in ascending order

Interactive Editor

function merge(nums1, m, nums2, n) {
// Your code here

}

Tests: 5 total

Hints

Hint 1: Direction Matters

If you merge from the beginning, you risk overwriting elements in nums1 that you haven't processed yet. Consider merging from the end instead, where the empty space is.

Hint 2: Three Pointers

Use three pointers:

• p1 pointing to the last valid element in nums1 (index m - 1)
• p2 pointing to the last element in nums2 (index n - 1)
• writeIndex pointing to the last position in nums1 (index m + n - 1)

Compare elements at p1 and p2, place the larger one at writeIndex, then move the appropriate pointers.

Hint 3: When to Stop

You only need to continue while p2 >= 0. If p2 becomes negative first, the remaining elements in nums1 are already in their correct positions. But if p1 becomes negative first, you still need to copy remaining elements from nums2.

Solution

View Solution Explanation

function merge(nums1, m, nums2, n) {
  let p1 = m - 1;      // Last valid element in nums1
  let p2 = n - 1;      // Last element in nums2
  let writeIndex = m + n - 1;  // Last position in nums1

  while (p2 >= 0) {
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[writeIndex] = nums1[p1];
      p1--;
    } else {
      nums1[writeIndex] = nums2[p2];
      p2--;
    }
    writeIndex--;
  }

  return nums1;
}

Why Merge from the End?

The key insight is that nums1 has empty space at the end, not the beginning. If we merge from the start, we'd overwrite elements we still need. By merging from the end, we fill the empty space first.

How It Works

1. Start all three pointers at the end of their respective regions
2. Compare nums1[p1] and nums2[p2]}, place the larger value at writeIndex
3. Move the pointer of whichever element we just placed, and move writeIndex
4. Continue until we've placed all elements from nums2

Why Only Check p2 >= 0?

If p2 goes negative first, all of nums2 is merged and nums1's remaining elements are already in place.

If p1 goes negative first, the condition p1 >= 0 && nums1[p1] > nums2[p2] fails, so we copy from nums2, which is correct.

Complexity: O(m + n) time, O(1) space.