You get two arrays sorted in non-decreasing order: nums1 with m real elements followed by n zeros (empty slots), and nums2 with n elements. Merge nums2 into nums1 so that nums1 holds all m + n values in sorted order. Modify nums1 in place and return nothing.
[1,2,3] and [2,5,6] are combined inside nums1.nums1 has no real elements, so the result is just nums2.- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -10^9 <= nums1[i], nums2[j] <= 10^9
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The lazy way copies nums2 into the tail and sorts, which is O((m+n) log(m+n)). A normal front-to-back merge needs a temporary array because it would overwrite unread values. The free slots are at the end of nums1, so merge backwards: the largest remaining value always goes into the last empty position, and we never overwrite something we still need.
Algorithm
- Set
i = m - 1,j = n - 1,w = m + n - 1. - While
j >= 0: ifi >= 0andnums1[i] > nums2[j], writenums1[i]atwandi--. - Otherwise write
nums2[j]atwandj--. - Decrease
weach time. Whenj < 0, the rest ofnums1is already in place.
O(m + n)Space: O(1)nums2 has elements left: leftover nums1 values are already in the right spots. Many candidates add an unnecessary second copy loop.class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: i, j, w = m - 1, n - 1, m + n - 1 # w = next slot to fill, from the back while j >= 0: if i >= 0 and nums1[i] > nums2[j]: nums1[w] = nums1[i] i -= 1 else: nums1[w] = nums2[j] j -= 1 w -= 1