Merge Sorted Array

1. Define the problem

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. nums1 has a length of m + n, where the first m elements are the real values and the last n elements are 0 and should be ignored. nums2 has a length of n. Merge nums1 and nums2 into a single array sorted in non-decreasing order , stored inside nums1. Work backward from the end of both arrays with two pointers, placing the larger remaining value into the last free slot of nums1 — this avoids overwriting values in nums1 that have not been read yet.

Constraints

nums1.length == m + n
nums2.length == n
0 ≤ m, n ≤ 200
1 ≤ m + n ≤ 200
-10⁹ ≤ nums1_i, nums2_j ≤ 10⁹

Example

Inputnums1 = [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 merge are [1, 2, 3] and [2, 5, 6], and the result is [1, 2, 2, 3, 5, 6].

2. Know the words first

In plain terms

Non-decreasing order: Each value is greater than or equal to the one before it, so repeats are allowed — for example, [1, 2, 2, 5] is in non-decreasing order.

3. Visualize the solution

Fill nums1 back-to-front with two pointers

Statusinit

i=2 (value 3), j=2 (value 6), write=5. Compare 3 vs 6 — 6 is larger, write it to index 5.

What happens in this step

i = 2 (value 3), j = 2 (value 6)
compare nums1[i]=3 vs nums2[j]=6

6 is larger, so write 6 into nums1[write=5] and move j left to 1.

Step 1 of 5

Steps to visualize

Point i at the last real element of nums1 (index m - 1) and j at the last element of nums2 (index n - 1).
Point write at the last slot of nums1 (index m + n - 1).
Compare nums1_i and nums2_j; copy the larger one into nums1_write and move that pointer left.
Repeat, always writing from the back, until nums2 is fully consumed.
Any remaining nums1 values are already in place, so the merge is done once j < 0.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill nums1 back-to-front with two pointers

Statusinit

i=2 (value 3), j=2 (value 6), write=5. Compare 3 vs 6 — 6 is larger, write it to index 5.

What happens in this step

i = 2 (value 3), j = 2 (value 6)
compare nums1[i]=3 vs nums2[j]=6

6 is larger, so write 6 into nums1[write=5] and move j left to 1.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

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

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

  return nums1;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3`	`[1, 2, 2, 3, 5, 6]`	example from the docstring
`nums1 = [1, 2, 3], m = 3, nums2 = [], n = 0`	`[1, 2, 3]`	nums2 is empty, nothing to merge
`nums1 = [0, 0, 0], m = 0, nums2 = [2, 5, 6], n = 3`	`[2, 5, 6]`	nums1 has no real values, all placeholders
`nums1 = [1, 2, 4, 5, 6, 0, 0, 0], m = 5, nums2 = [2, 4, 6], n = 3`	`[1, 2, 2, 4, 4, 5, 6, 6]`	duplicate values interleaved between the two arrays
`nums1 = [2, 0], m = 1, nums2 = [1], n = 1`	`[1, 2]`	smallest non-trivial case, one element in each array
`nums1 = [4, 5, 6, 0, 0, 0], m = 3, nums2 = [1, 2, 3], n = 3`	`[1, 2, 3, 4, 5, 6]`	all nums2 values are smaller than all nums1 values

Merge Sorted Array