1. Merge Sorted Array (LeetCode)
Model answer
The task
Combine two already sorted arrays into one sorted array, placing the result in the first array. The first array has enough spare capacity to hold all elements from both arrays.
Key idea
Fill the first array from right to left. Comparing the largest remaining elements avoids overwriting values in the first array that have not yet been processed.
Approach
- Set pointers to the last valid elements of both arrays.
- Set a write pointer to the last slot in the first array.
- While the second array still has elements, compare the values at the two read pointers.
- Write the larger value at the write pointer, then move the corresponding read pointer and the write pointer left.
- Any remaining elements from the second array are copied into the first. Remaining elements from the first are already in place.
class Solution:
def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
"""Merge nums2 into nums1 in-place, keeping nums1 sorted."""
i = m - 1 # Last initialized element in nums1
j = n - 1 # Last element in nums2
write = m + n - 1 # Last available position in nums1
# Fill from the back so unread nums1 elements are not overwritten.
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[write] = nums1[i]
i -= 1
else:
nums1[write] = nums2[j]
j -= 1
write -= 1
Complexity:
- Time: O(m + n), since each element is considered at most once.
- Space: O(1), because the merge modifies the first array directly.
Common follow-ups
- What if the arrays are sorted in descending order? Reverse the comparison or adapt the traversal direction.
- What if the result must go into a separate array? Use two forward pointers and allocate O(m + n) extra space.
- What if either array is empty? The loop naturally handles it; if the second is empty, the first is already complete.
- Why merge from the end? Writing from the front could overwrite unprocessed elements in the first array.