Problem. Given a list nums, move all zeros to the end in place, keeping the relative order of the non-zero
values.
[0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]
ML context. This is stable partitioning, the operation behind compacting a batch: move real tokens to the front and padding to the back, keep valid detections ahead of suppressed ones, or pack non-empty rows of a sparse buffer together without reordering them.
It's an "Easy" problem that teaches a pattern used everywhere in this roadmap: a read pointer that visits every element and a write pointer that marks where the next kept element goes.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Must the non-zero order be kept? | Yes | Rules out swapping zeros with the end |
| In place? | Yes, O(1) extra | Rules out building a new list (as the final answer) |
| Values other than zero? | Any integers | Only == 0 matters |
| n? | Up to 10⁴ (or 10⁶) | Rules out shifting elements repeatedly |
2. Step 2: Brute force
Two natural brute forces, with different costs.
Brute force A: remove zeros and append them. list.remove(0) shifts everything after it; doing it z times
costs O(n · z).
def move_zeroes_remove(nums):
zeros = nums.count(0)
for _ in range(zeros):
nums.remove(0) # O(n): finds the first 0 and shifts the rest left
nums.append(0)
nums = [0, 1, 0, 3, 12]
move_zeroes_remove(nums)
assert nums == [1, 3, 12, 0, 0]
print("remove-and-append works: O(n·z) time")
Brute force B: build a copy. Collect non-zeros, pad with zeros, copy back. O(n) time, but O(n) extra space, which breaks the in-place constraint.
def move_zeroes_copy(nums):
kept = [x for x in nums if x != 0]
nums[:] = kept + [0] * (len(nums) - len(kept)) # O(n) extra memory
nums = [0, 1, 0, 3, 12]
move_zeroes_copy(nums)
assert nums == [1, 3, 12, 0, 0]
print("copy version works: O(n) time, O(n) extra space")
So brute force A is in place but slow when there are many zeros (all zeros: O(n²)); brute force B is fast but uses memory. The optimisation must get both: O(n) time and O(1) space.
3. Step 3: Optimise: a read pointer and a write pointer
Look at what the copy did: it walked the list once and wrote each non-zero to the next free slot of a new list. We can do the same writes into the same list: the write position never gets ahead of the read position, so we never overwrite a value we haven't read yet.
import random
def move_zeroes(nums):
write = 0
for read in range(len(nums)):
if nums[read] != 0:
nums[write] = nums[read] # write <= read, so nothing unread is lost
write += 1
for i in range(write, len(nums)): # everything after the kept values becomes 0
nums[i] = 0
def reference(nums):
kept = [x for x in nums if x != 0]
return kept + [0] * (len(nums) - len(kept))
for case in ([], [0], [1], [0, 0, 1], [1, 2, 3], [0, 1, 0, 3, 12], [4, 0, 5, 0, 0, 6]):
nums = list(case)
move_zeroes(nums)
assert nums == reference(case), case
rng = random.Random(11)
for _ in range(500):
case = [rng.choice([0, 0, rng.randint(-5, 5)]) for _ in range(rng.randint(0, 20))]
nums = list(case)
move_zeroes(nums)
assert nums == reference(case)
print("read/write pointers: O(n) time, O(1) space, order kept")
- Time: one read pass plus filling the tail: O(n).
- Space: O(1).
- Invariant (say it out loud): "everything before
writeis the non-zero values seen so far, in order." Each step keeps it true; whenreadreaches the end, the invariant is the answer.
Quick check
Why can't the write pointer overwrite a value that hasn't been read yet?
Show the answer
B. write only advances when a non-zero is read, so write ≤ read at all times; it only ever writes into positions already read — Maintaining write ≤ read is what makes the in-place version safe.
4. When writes are expensive: swap only when needed
The version above writes every non-zero value, even the ones already in the right place. In an array of a million values with ten zeros near the end, it does about a million writes to move about ten things.
A variant swaps the non-zero into the write slot only when they differ. Values already in place aren't rewritten. Swapping (rather than overwriting) also means there's no tail-filling pass: the zeros travel backwards naturally.
import random
def move_zeroes_swap(nums):
write = 0
writes = 0
for read in range(len(nums)):
if nums[read] != 0:
if read != write: # already in place? then skip
nums[write], nums[read] = nums[read], nums[write]
writes += 2
write += 1
return writes
def reference(nums):
kept = [x for x in nums if x != 0]
return kept + [0] * (len(nums) - len(kept))
rng = random.Random(12)
for _ in range(500):
case = [rng.choice([0, rng.randint(1, 9)]) for _ in range(rng.randint(0, 20))]
nums = list(case)
move_zeroes_swap(nums)
assert nums == reference(case)
late_zeros = list(range(1, 1_000_001))
for i in range(-20, -10):
late_zeros[i] = 0 # ten zeros, followed by ten more values
writes = move_zeroes_swap(late_zeros)
print("writes with zeros near the end:", writes) # 10 swaps of 2 writes each
assert writes == 20
assert move_zeroes_swap([0] + list(range(1, 11))) == 20 # a zero first: every value moves
Both versions are O(n) time and O(1) space. The difference is the constant: which matters only when the constraint says writes are costly (flash storage, memory shared across processes, very large records). Name the trade-off; don't overclaim it: with a zero at the front, the swap version moves everything too.
5. When the constraints change
| If the constraint becomes… | Best approach | Time | Extra space | Note |
|---|---|---|---|---|
| Order must be kept (classic) | Read/write pointers | O(n) | O(1) | |
| Writes are expensive | Swap only when read ≠ write | O(n) | O(1) | fewer writes when zeros are late |
| Order doesn't matter | Swap each zero with the last non-zero | O(n) | O(1) | at most z swaps |
| Must not modify the input | Build a filtered copy | O(n) | O(n) | |
| Keep only values passing any test (not just ≠ 0) | Same read/write pass with a predicate | O(n) | O(1) | stable filter |
| NumPy array, speed matters | Boolean mask: x[x != 0] + zeros |
O(n), vectorised | O(n) |
The order-doesn't-matter row shows how a relaxed constraint enables a cheaper method: walk two pointers inward and swap each zero on the left with a non-zero on the right. That does at most one swap per zero, but scrambles the order, so it's only allowed when order doesn't matter.
import random
def move_zeroes_unordered(nums):
"""Zeros to the end; the order of non-zeros is NOT preserved."""
left, right = 0, len(nums) - 1
while left < right:
if nums[left] != 0:
left += 1
elif nums[right] == 0:
right -= 1
else:
nums[left], nums[right] = nums[right], nums[left] # one swap fixes one zero
rng = random.Random(13)
for _ in range(500):
case = [rng.choice([0, rng.randint(1, 9)]) for _ in range(rng.randint(0, 20))]
nums = list(case)
move_zeroes_unordered(nums)
nz = sum(1 for x in case if x != 0)
assert sorted(nums[:nz]) == sorted(x for x in case if x != 0) # same values, any order
assert all(x == 0 for x in nums[nz:])
print("unordered version works with at most one swap per zero")
The general tool: a stable filter in place
The read/write pass isn't really about zeros: it keeps the elements that pass a test, in order. That's how you'd compact padding out of a token batch, or keep only detections above a score threshold:
def filter_in_place(items, keep):
write = 0
for x in items:
if keep(x):
items[write] = x
write += 1
del items[write:] # drop the tail instead of zero-filling it
return items
PAD = 0
tokens = [101, 7592, PAD, 2088, PAD, PAD, 102]
assert filter_in_place(tokens, lambda t: t != PAD) == [101, 7592, 2088, 102]
detections = [("cat", 0.91), ("dog", 0.12), ("car", 0.66), ("cup", 0.05)]
assert filter_in_place(detections, lambda d: d[1] >= 0.5) == [("cat", 0.91), ("car", 0.66)]
print("stable in-place filter works for any test")
Quick check
The interviewer says the order of non-zero values doesn't matter. What changes?
Show the answer
A. You can swap each zero with a non-zero from the end, doing at most one swap per zero, instead of shifting every non-zero forward; still O(n) time and O(1) space, but fewer writes — Relaxing the stability constraint unlocks a cheaper partition with at most z swaps.
6. Saying it out loud
"Removing zeros one by one shifts the list each time: O(n·z), up to O(n²). Building a filtered copy is O(n) but uses O(n) memory. Instead I'll keep a write pointer: every non-zero is written to the next slot, which never gets ahead of the read pointer, then I fill the rest with zeros. O(n) time, O(1) space, order preserved. If writes were expensive I'd swap only when read ≠ write; if order didn't matter I'd swap zeros with non-zeros from the end."
Check yourself
- What are the costs of the two brute forces, and which constraint does each violate?
- What is the invariant of the read/write pass?
- Why is it safe to write into the same list you're reading?
- When does the swap-only-if-needed variant save writes, and when doesn't it?
- What does "order doesn't matter" unlock?
- How does the same pass compact padding tokens out of a batch?
Answers
- Remove-and-append: O(n·z) time, too slow with many zeros. Copy: O(n) time but O(n) extra space, breaking "in place".
- Everything before
writeis the non-zero values seen so far, in their original order. writeonly advances after reading a non-zero, sowrite ≤ read: it never overwrites an unread value.- When the zeros are near the end, values before the first zero are never rewritten. With a zero at the front, every value moves anyway.
- Swapping each zero with a non-zero from the end: at most one swap per zero, but the order of non-zeros changes.
- Use the predicate "token isn't padding", write kept tokens forward, and truncate the tail.