Merge Sorted Array

You are given two non-decreasing integer arrays. The first array nums1 has a length of m + n, where the first m elements are valid and the last n elements are empty placeholders. The second array nums2 has length n and is fully valid.

Your task is to merge nums2 into nums1 so that nums1 becomes fully sorted. The merge must be in-place.

A naive merge from the front overwrites data you still need. The key is to work from the end.

Why this is worth learning

The spare slots are at the right, so make the right-hand suffix final first. This is an overwrite-order problem, not a reason to allocate another merged array.

Before coding: one-minute experiment

With nums1=[2,4,0,0], m=2, nums2=[1,3], n=2, what are the four values written from right to left?

Function signature

func MergeSortedArray(nums1 []int, m int, nums2 []int, n int)

Inputs / outputs

• nums1: length m + n, sorted in its first m positions.
• m: number of valid elements in nums1.
• nums2: length n, sorted in all positions.
• n: number of elements in nums2.
• Return: nothing. nums1 must be modified in-place to contain the merged result.

Example

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

After merge: nums1 = [1,2,2,3,5,6]

Constraints

• 0 <= m, n <= 100_000
• len(nums1) == m + n
• nums1[0:m] is sorted
• nums2 is sorted

Core idea (near-solution)

Use three pointers from the end:

• i = m - 1 points at the last valid element of nums1.
• j = n - 1 points at the last element of nums2.
• write = m + n - 1 points at the last slot in nums1.

Invariant: everything after write is already in its final, sorted position.

At each step, place the larger of nums1[i] and nums2[j] at nums1[write], then decrement the pointer you used. This works because the largest remaining element must belong at the end.

Algorithm (step-by-step)

1. Initialize i = m-1, j = n-1, write = m+n-1.
2. While j >= 0 (there is still data to place from nums2):
   • If i >= 0 and nums1[i] > nums2[j], write nums1[i] to nums1[write], then i--.
   • Otherwise, write nums2[j] to nums1[write], then j--.
   • Always decrement write after a write.
3. When j < 0, the merge is complete.

Correctness sketch

Let i and j be the last unread indices and w=i+j+1 the next destination. Initially the final suffix is empty. Among the unread values, sortedness makes max(nums1[i], nums2[j]) the largest; placing it at w extends the correct suffix by one. While j>=0, w>i, so writing cannot destroy an unread value of nums1. If i<0, only nums2 remains. Every iteration consumes one value. When j<0, w=i and the remaining nums1 prefix is already in its final positions. This is the stopping argument; the three pointers do not need to meet.

Trace (hand walkthrough)

Example input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

After merge: nums1 = [1,2,2,3,5,6]

Walk:
- i=2 (3), j=2 (6), write=5 -> place 6: nums1=[1,2,3,0,0,6], j=1, write=4
- i=2 (3), j=1 (5), write=4 -> place 5: nums1=[1,2,3,0,5,6], j=0, write=3
- i=2 (3), j=0 (2), write=3 -> place 3: nums1=[1,2,3,3,5,6], i=1, write=2
- i=1 (2), j=0 (2), write=2 -> place 2 from nums2: nums1=[1,2,2,3,5,6], j=-1 stop

Pitfalls to avoid

• Merging from the front (overwrites nums1 data).
• Forgetting that nums1 must have length m+n, not merely spare capacity. The final n indexed slots are writable storage.
• Stopping when i < 0 (you still must copy remaining nums2 elements).

Debugging lens

Use [2,0] and [1] to expose a front-writing overwrite. Also merge an empty first prefix: checking i>=0 must precede reading nums1[i]. The destination has length m+n, not merely unused capacity.

Complexity

• Time: O(m + n)
• Extra space: O(1)

Implementation notes (Go)

• Modifying nums1[i] updates the caller's slice (the underlying array is shared).
• Always check i >= 0 before reading nums1[i].

Reconstruction checkpoint

With nums1=[2,4,0,0], m=2, nums2=[1,3], n=2, what are the four values written from right to left?

Return to Array & String · Module quiz