Move Zeroes
How to push every zero to the end of an array, in place, in one pass — while every other number keeps its original relative order.
The job
You have an array of numbers, some of which are zero. Move every zero to the end, without using extra space, and without changing the relative order of the non-zero numbers.
The obvious way
Build a brand new array: copy every non-zero number into it first, then pad the rest with zeros, then copy it back over the original.Works, but costs a second array the same size as the input — not truly in place.
The idea
Keep two positions: `write`, where the next non-zero number belongs, and `read`, which scans every position in order. Whenever `read` finds a non-zero number, swap it into `write`'s slot and advance both. Zero is never actively moved — it just gets left behind by every swap.
Think of it like this. Tidying a shelf of mixed books and empty slots by walking it once left to right: every time you find a book, you slide it into the next open spot near the front. You never touch an empty slot directly — it just naturally ends up at the back as books slide past it.
Partitioning in place with two pointers
5 numbers, some zero. Push every zero to the end, keeping the other numbers in their original relative order.
def move_zeroes(nums):
write = 0
for read in range(len(nums)):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write += 1This run
After the scan, the first 3 positions hold every non-zero number in its original order, and the last 2 are all zero — done in one pass, no extra array.
The names you just watched
write and read
`read` scans every position once. `write` only ever advances when something is actually placed — so it always points at the boundary between "done" and "not yet placed."
A swap, not a shift
Swapping `write` and `read` (instead of shifting everything between them) is what keeps the whole pass at O(n) instead of O(n²) — no element is ever moved more than a constant number of times.
Zero moves for free
The zero at `write`'s old slot is never targeted directly. Every swap that places a real number pushes exactly one zero one step closer to the back.
How to spot this shape
The tell: You need to partition an array in place around a condition (keep this, discard/park that) while preserving the relative order of what you keep.
Reach for it when
- The problem explicitly says "in place" or "O(1) extra space."
- One category of element needs to be pushed to the end (or front) rather than removed.
- The relative order of the kept elements must be preserved.
- A brute-force answer builds a second array and copies into it.
Not this when
- Order does not need to be preserved — sorting or counting is simpler.
- You need a stable partition around TWO thresholds, not one — that needs a second write pointer (see Sort Colors).
- Elements need to be removed entirely rather than relocated within the same array.
- The array is not random-access (a linked list), where swapping is a different operation entirely.
Practice
6 problemsThe lesson, exactly. A write pointer only advances when something actually needs writing.
Same write/read shape, but instead of preserving zeros you skip a specific value entirely — no swap needed, just a copy.
Same write/read shape again, but the write condition compares against the last KEPT value instead of checking for a specific number.
The write condition now compares against the value two slots back, allowing each value up to twice.
A three-way version of this exact partition idea — one read pointer, but now two write pointers, one from each end.
Swap the write/read condition to "is this number even" — everything else about the walk is identical.