TL;DR
Slow/fast two pointers with swaps (one pass, in place) — O(n) time, O(1) space.
Approach 1 — Brute force: rebuild in a new list
Collect the nonzeros, count the zeros, and write the reconstructed array back.
def moveZeroes(nums: list[int]) -> None:
nonzeros = [x for x in nums if x != 0]
zeros = len(nums) - len(nonzeros)
nums[:] = nonzeros + [0] * zeros
- Time:
O(n).
- Space:
O(n) for the temporary list.
The runtime is fine; the in-place requirement rules it out. The problem forbids copying the array, and the temporary list is exactly the O(n) scratch space it disallows.
Approach 2 — Overwrite then back-fill zeros
You never need to move zeros, only nonzeros have destinations. Copy each nonzero forward to the next write slot, then overwrite everything after the last write slot with zeros.
def moveZeroes(nums: list[int]) -> None:
write = 0
for x in nums:
if x != 0:
nums[write] = x
write += 1
for i in range(write, len(nums)):
nums[i] = 0
Walkthrough on nums = [0,1,0,3,12]:
| read x | action | nums after | write |
|---|
| 0 | skip | [0,1,0,3,12] | 0 |
| 1 | nums[0] = 1 | [1,1,0,3,12] | 1 |
| 0 | skip | [1,1,0,3,12] | 1 |
| 3 | nums[1] = 3 | [1,3,0,3,12] | 2 |
| 12 | nums[2] = 12 | [1,3,12,3,12] | 3 |
Back-fill indices 3..4 with zeros → [1,3,12,0,0].
- Time:
O(n) — two passes.
- Space:
O(1).
Writes: one per nonzero plus one per trailing slot — up to n total even when the array needs no change.
Approach 3 — One-pass swap (slow/fast pointers)
Maintain the invariant: nums[0:slow] holds exactly the nonzeros seen so far, in order, and nums[slow:fast] is all zeros. When fast finds a nonzero, swapping it with nums[slow] extends the nonzero prefix by one and relocates a zero in the same move. No back-fill pass, and no writes while the prefix is already correct.
def moveZeroes(nums: list[int]) -> None:
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
Walkthrough on nums = [0,1,0,3,12]:
| fast | nums[fast] | action | nums after | slow |
|---|
| 0 | 0 | skip | [0,1,0,3,12] | 0 |
| 1 | 1 | swap idx 0 ↔ 1 | [1,0,0,3,12] | 1 |
| 2 | 0 | skip | [1,0,0,3,12] | 1 |
| 3 | 3 | swap idx 1 ↔ 3 | [1,3,0,0,12] | 2 |
| 4 | 12 | swap idx 2 ↔ 4 | [1,3,12,0,0] | 3 |
Result: [1,3,12,0,0]. The middle region nums[slow:fast] was zeros at every step, which is why each swap parks a zero correctly. When the array has no zeros, slow == fast throughout and every swap is a self-swap with no net data movement, satisfying the “minimize operations” follow-up (add an if slow != fast guard to skip even those writes).
- Time:
O(n) — single pass.
- Space:
O(1).
This is the partition step of quicksort (Lomuto scheme) specialized to the predicate “is nonzero”: an in-place partition that is stable for the kept side.
Common pitfalls
- Moving zeros instead of nonzeros (e.g., deleting zeros and appending) —
list.remove inside a loop is O(n^2) and skips elements while iterating.
- Breaking relative order by swapping nonzeros with the last zero from the back — order of the nonzeros must be preserved, so the write frontier must move left-to-right.
- Forgetting the back-fill pass in Approach 2, leaving stale values (like the trailing
3,12 mid-walkthrough) behind the write pointer.
- Returning a new list — the judge checks the mutated
nums, and the signature returns None.
Pattern takeaway
The slow/fast pointer pair is an in-place stable partition: slow marks the boundary of the output built so far, and fast scans for the next element that belongs in it. State the invariant of the region between the pointers before coding. If that region is provably all rejects, a single swap per accepted element is both correct and write-minimal. The same skeleton solves Remove Duplicates, Remove Element, and quicksort’s partition.