Merge two sorted arrays in place

Problem Given two sorted integer arrays where the first array has trailing empty slots exactly big enough to hold the second, merge the second into the first in place so the result is one sorted array.

Input / Output

• Input: nums1 of size m+n (first m values sorted, last n slots empty), nums2 of size n (sorted).
• Output: nums1 containing all m+n values in sorted order; no extra array allowed.

Constraints

• 0 <= m, n <= 2*10^5; required O(m+n) time, O(1) extra space.

Example

• nums1 = [1,2,3,0,0,0] (m=3), nums2 = [2,5,6] → [1,2,2,3,5,6]

Expected approach

• Three pointers from the back: i = m-1, j = n-1, k = m+n-1. Write the larger of nums1[i]/nums2[j] at position k and decrement. Filling from the end means nothing unread is ever overwritten. Finish by copying any remaining nums2 elements. O(m+n) time, O(1) space.