Move Zeroes

easyArrayTwo PointersTwo PointersTime: O(n) · Space: O(1)

easyTime: O(n)Space: O(1)

The shape of the problem

Move every 0 to the end of the array while keeping the non-zero elements in their original order. Must be in-place.

Signals to notice

in-place reorderingpreserve relative orderstable partition

Brute force first

Collect non-zeros into a new array, pad with zeros, copy back. O(n) time but O(n) extra space — and the problem explicitly wants in-place.

The key insight

The positions of non-zeros relative to each other never change. That means you can pack them into the prefix in the order you see them, and the suffix is guaranteed to be all zeros.

Trace it on `nums=[0,1,0,3,12]`

r=0 w=0  nums[r]=0  skip
r=1 w=0  nums[r]=1  write → [1,1,0,3,12]  w=1
r=2 w=1  nums[r]=0  skip
r=3 w=1  nums[r]=3  write → [1,3,0,3,12]  w=2
r=4 w=2  nums[r]=12 write → [1,3,12,3,12] w=3
fill 3..4 with 0    → [1,3,12,0,0]

What must stay true

After each step of the loop, `nums[0..write)` contains exactly the non-zeros seen so far, in their original order.

Shape of the loop

w = 0
for r in 0..n-1:
  if nums[r] != 0:
    nums[w] = nums[r]
    w += 1
for i in w..n-1: nums[i] = 0

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Swapping instead of overwriting, and doing it when `read == write`. You swap an element with itself, which is harmless but wastes writes. Worse: swapping on every iteration regardless of value scrambles order.

Two Pointers Pattern