Merge Sorted Array
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Two sorted arrays are given: nums1 with m real values followed by n empty slots, and nums2 with n values. Merge nums2 into nums1 in place so that nums1 ends up fully sorted.
Examples
Constraints
- • nums1.length == m + n
- • 0 <= m, n <= 200
- • Both inputs are sorted in non-decreasing order
Hints & approach
Hint 1
Merging from the front would overwrite values of nums1 you still need.
Hint 2
The empty space is at the back of nums1. Fill it from the back.
Approachtry the hints first
Use three pointers: i = m - 1 (last real value in nums1), j = n - 1 (last in nums2) and w = m + n - 1 (write position). While j >= 0, write the larger of nums1[i] and nums2[j] into nums1[w] and move the corresponding pointers left. Writing from the back never overwrites unread data, and any leftover nums1 values are already in place.
Time O(m + n) · Space O(1)
