The pattern behind this problem is the swap-partition: a slow write frontier keeps the boundary between the kept non-zeros and the zeros still being processed, while a fast scanner races ahead and is the only thing that moves each step. The insight is that zeros never need to be deleted or pushed — they only need to be swapped past. Every non-zero that the scanner finds swaps into the frontier slot and pushes the frontier one step right, so the zero that was there silently drifts toward the tail. Because a swap never lifts a non-zero over another non-zero, the relative order of the non-zeros is preserved for free — and because the scanner passes exactly once, the whole pass is linear.
Brute Force: Shift Zeros to the End
Time O(n²)Space O(1)The most literal reading of the problem is to find a zero and physically haul it to the back of the array. Scan with one index; whenever a zero sits at that index, shift everything after it one slot left and drop a zero into the tail slot that just opened up. After the shift, the same index must be re-inspected — the element that slid into the vacated slot could itself be a zero — so i only advances on the else branch. Each manufactured trailing zero is never looked at again, hence the shrinking logical tail.
class Solution: def moveZeroes(self, nums: list[int]) -> None: n = len(nums) moved = 0 # how many zeros are already pinned to the tail i = 0 while i < n - moved: if nums[i] == 0: # Shift the tail left one slot, then pin a zero at the back. for j in range(i, n - 1 - moved): nums[j] = nums[j + 1] nums[n - 1 - moved] = 0 moved += 1 else: i += 1Why it is quadratic: each zero costs a shift of the entire remaining tail. An input that is mostly zeros moves almost every element almost every time — with n zeros, the first grabs n - 1 shifts, the next n - 2, and so on, which sums to about n² / 2 shifts in the worst case. The same tail is walked over and over even though each element only deserved one look.
Two Pointers: Swap-Partition
OptimalTime O(n)Space O(1)Both pointers start at index 0. slow is the write frontier — the index of the first zero slot, which also doubles as the count of non-zeros handled so far. fast scans left to right exactly once, and at every stop it asks one question: is this a zero? A zero is skipped — slow stays frozen. A non-zero is swapped with the frontier slot and slow advances by one. The swap is the key trick: it simultaneously packs the non-zero into the kept prefix and kicks the zero toward the right side, so neither physical deletion nor a second pass is ever needed.
class Solution: def moveZeroes(self, nums: list[int]) -> None: slow = 0 for fast in range(len(nums)): if nums[fast] != 0: # Push this non-zero onto the packed prefix and let the # zero it displaces drift right of the frontier. nums[slow], nums[fast] = nums[fast], nums[slow] slow += 1Watch the markers on the file example, [0, 1, 0, 3, 12]: each non-zero swaps into the frontier slot and the swapped-out zero drifts right, giving [1, 3, 12, 0, 0].
nums — one array, written in place
a non-zero is never moved twice and never reordered — slow advances one slot per swap, so the kept prefix always packs left in its original relative order
The rule that makes this O(n): a slow write frontier holds the index of the first zero slot, and a fast scanner does the only move of each step. slow starts at 0, pointing at the leftmost slot. As fast reads a non-zero, that value is swapped into slot slow and slow advances by one; a zero is only skipped. After one pass every non-zero sits at the front in its original order and every zero has drifted right.
Watch the longer run [0, 0, 1, 0, 5, 0, 0, 8]: leading and middle zeros are skipped without moving the frontier, every non-zero (including the 8 that starts at the far right) is written exactly once, and the relative order [1, 5, 8] survives intact.
nums — one array, written in place
a non-zero is never moved twice and never reordered — slow advances one slot per swap, so the kept prefix always packs left in its original relative order
Richer example: [0, 0, 1, 0, 5, 0, 0, 8]. Two leading zeros mean the frontier slow = 0 will not move for the first two reads. Watch how a run of zeros is skipped as one unit while a single non-zero advances the frontier exactly one slot.
Why it is linear: fast advances once per element and does a constant O(1) comparison; slow advances once per non-zero and does a constant O(1) swap. Every cell is read at most twice (once read, at most once swapped), giving O(n) total time with no re-scanning — a dramatic contrast to the shift-based brute force that re-walks the same tail. Space is O(1): the swap happens on the array itself, and the only other state is two indices. Correctness rests on the swap-partition invariant: all cells left of slow are non-zeros in their original relative order, so the swap at slow always lands into the first zero slot and never reorders anything. An edge case takes care of itself — a single element, zero or not, leaves the frontier unmoved and the array unchanged. A common fill-zeros variant writes the first slow non-zeros and then overwrites the tail with zeros; it is equally O(n) but does more writes per zero than a swap, which is why swap is preferred when trying to minimize operations.