TL;DR
Three pointers merging backward from the end of nums1 — O(m + n) time, O(1) extra space.
Approach 1 — Brute force: copy and sort
Copy nums2 into the trailing slots, then sort the whole array. This ignores the fact that both halves are already sorted.
def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
for i in range(n):
nums1[m + i] = nums2[i]
nums1.sort()
- Time:
O((m + n) log (m + n)) — the sort dominates.
- Space:
O(1) extra beyond the sort’s internals (Timsort uses up to O(m + n) scratch).
With m + n <= 200 the constraints let this pass, but the follow-up asks for linear time, which means using the pre-sorted inputs instead of re-sorting.
Approach 2 — Forward merge with a buffer
Merging two sorted lists is a single linear pass: repeatedly take the smaller of the two front elements. This is the merge step of merge sort. Merging forward directly into nums1 would overwrite unread values, so copy nums1’s real prefix into a buffer first.
def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
first = nums1[:m]
i = j = 0
for k in range(m + n):
take_first = j >= n or (i < m and first[i] <= nums2[j])
if take_first:
nums1[k] = first[i]
i += 1
else:
nums1[k] = nums2[j]
j += 1
Walkthrough on nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6]:
| k | compare | write | i | j |
|---|
| 0 | 1 vs 2 | 1 | 1 | 0 |
| 1 | 2 vs 2 | 2 (from first, ties keep stability) | 2 | 0 |
| 2 | 3 vs 2 | 2 | 2 | 1 |
| 3 | 3 vs 5 | 3 | 3 | 1 |
| 4 | first empty | 5 | 3 | 2 |
| 5 | first empty | 6 | 3 | 3 |
Result: [1,2,2,3,5,6].
- Time:
O(m + n) — one write per slot.
- Space:
O(m) for the buffer.
Approach 3 — Backward merge, three pointers
The free space in nums1 sits at the end, so merge from the largest elements down. Writing at index m + n - 1 and moving left can never overwrite a nums1 value that hasn’t been consumed, because the write pointer stays to the right of the read pointer.
def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
i, j, k = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
Note the loop runs only while j >= 0: once nums2 is exhausted, the remaining nums1 prefix is already sorted and already in place.
Walkthrough on nums1 = [1,2,3,0,0,0], nums2 = [2,5,6] (i=2, j=2, k=5):
| step | compare | write at k | nums1 after | i | j |
|---|
| 1 | 3 vs 6 → take 6 | k=5 | [1,2,3,0,0,6] | 2 | 1 |
| 2 | 3 vs 5 → take 5 | k=4 | [1,2,3,0,5,6] | 2 | 0 |
| 3 | 3 vs 2 → take 3 | k=3 | [1,2,3,3,5,6] | 1 | 0 |
| 4 | 2 vs 2 → take 2 (from nums2) | k=2 | [1,2,2,3,5,6] | 1 | -1 |
j < 0, loop ends; nums1[0..1] = [1,2] is already correct. Result: [1,2,2,3,5,6].
- Time:
O(m + n).
- Space:
O(1) — meets the follow-up.
Common pitfalls
- Merging forward without a buffer — you overwrite
nums1 values before reading them.
- Looping on
i >= 0 instead of j >= 0: leftover nums2 elements never get copied when nums1 empties first (e.g. m = 0).
- Forgetting the guard
i >= 0 in the comparison — Python’s negative indexing makes nums1[-1] silently read the last element instead of raising, producing wrong answers rather than a crash.
- Returning a new list instead of mutating
nums1 — the judge only looks at nums1.
Pattern takeaway
When merging into an array whose free space is at one end, fill from that end and move the pointers toward it, largest-first or smallest-first depending on which side the gap sits. Working from the gap end makes an in-place merge a plain two-pointer pass with no extra memory. The same idea appears in “squares of a sorted array” and any overwrite-safe in-place merge.