Push every zero to the end without changing the order of the rest, in place. A write pointer marks where the next non-zero belongs; swap each non-zero into it as you scan, and the zeros drift back in one O(n) pass with O(1) space.
▼The problem
LeetCode 283 (Easy). Given an integer array nums, move all the 0s to the end while keeping the relative order of the non-zero elements, in place (without making a copy of the array).
Examples (LeetCode's): [0,1,0,3,12] → [1,3,12,0,0] (the walkthrough example); [0] → [0].
The solution
def moveZeroes(nums):
write = 0
for read in range(len(nums)):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write += 1Transcript
Move Zeroes. Given a list of numbers, move every zero to the end. Keep the other numbers in their order, and work in place, without copying the list.
Take zero, one, zero, three, twelve. It becomes one, three, twelve, zero, zero. A list with a single zero stays as it is.
The easy way copies the non-zero numbers into a new list and pads it with zeros, but that's extra space. Bubbling each zero to the back, one swap at a time, stays in place but takes n squared steps.
Two pointers do better. Think of rowers filling a boat from the front. A write pointer marks the seat where the next non-zero number belongs. A read pointer scans every seat. Each non-zero it finds swaps into the write seat, and write moves up one. The empty seats drift to the back.
In code: write starts at zero. For each read index, if the number isn't zero, swap the two numbers and add one to write.
Back to our example. Read sees a zero: skip it. Read sees one: swap it into seat zero, and write moves to one. Another zero: skip. Three swaps into seat one, then twelve into seat two. One, three, twelve, zero, zero.
Every number is read once: linear time, constant space. Non-zero numbers are written in the order they're read, so their order holds. It's the same write pointer as removing duplicates.
Mark the write seat, scan, swap forward. That's Move Zeroes.