Merge Two Sorted Arrays In-Place

Problem

You are given two sorted integer arrays nums1 and nums2. nums1 has extra space at the end to hold nums2. Merge nums2 into nums1 in-place so the result is sorted.

Example

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

Constraints

• 0 ≤ m, n ≤ 200
• -10^9 ≤ nums1[i], nums2[i] ≤ 10^9

Key insight

Merge from the back to avoid overwriting elements. This gives O(m+n) time and O(1) extra space.