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
Dump nums2 into the filler slots, then sort the whole array. It ignores the fact that both halves are already sorted.
class Solution:
def merge(self, 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 this passes easily, so the constraints don’t kill it — the follow-up does: an interview expects you to exploit the pre-sorted inputs and hit linear time.
Approach 2 — Forward merge with a buffer
The insight: merging two sorted lists is a single linear pass — repeatedly take the smaller front element. This is the merge step of merge sort, the classical divide-and-conquer sorting algorithm. Merging forward into nums1 would clobber unread values, so copy nums1’s real prefix out to a buffer first.
class Solution:
def merge(self, 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 insight: 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 ahead of (to the right of) the read pointer.
class Solution:
def merge(self, 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, point your pointers toward the free space and fill it largest-first (or smallest-first, whichever direction the gap sits). Working from the gap end turns an “in-place merge is hard” problem into a plain two-pointer merge with zero extra memory — the same trick reappears in “squares of a sorted array” and any overwrite-safe in-place merge.