Merge Two Sorted Arrays

L3 Easy Two Pointers

Concept

Merging two sorted arrays can be done in one backward pass: fill the target array from its end so nothing is overwritten prematurely.

You are given nums1 (length m + n where the last n slots are zero placeholders) and nums2 (length n), each sorted in non-decreasing order. Merge nums2 into nums1 in place so the whole array ends up sorted. The first m slots of nums1 hold the real values. Return nothing.

Examples

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

→ [1, 2, 2, 3, 5, 6]

▸ nums1 = [1], m = 1, nums2 = [], n = 0

→ [1]

▸ nums1 = [0], m = 0, nums2 = [1], n = 1

→ [1]

Progressive Hints

Hint 1 · Nudge

Fill the big array from the back, so the largest values get decided first.

Hint 2 · Plan

Use three pointers: one at the last real value of nums1, one at the last value of nums2, and one at the very back write position. Place the bigger of the two current values at the write position and move inward. When one input runs out, copy the remaining values over.

Hint 3 · Approach

i = m - 1, j = n - 1, w = m + n - 1. While j >= 0: if i >= 0 and nums1[i] > nums2[j], place nums1[i] at w and decrement i; otherwise place nums2[j] at w and decrement j. Decrement w each step. Return nothing.

Output

// Run your code to see the output here.