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; O(m+n) time, O(1) extra space required.

Example

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