Move Zeroes

The question

You are given an array of numbers. Move all the zeroes to the end, keep the other numbers in their original order, and do it in place with no second array.

Explain it to a ten-year-old

A line of children, some holding a ball and some holding nothing. You want the children with balls at the front, in the same order they were in, and the empty-handed ones at the back. Walk down the line with one finger pointing at the first empty-handed spot. Every time you meet a child with a ball, swap them into that spot and move the finger one along. The children with balls stay in order because you only ever move them forward, never past each other.

flowchart TB
  a["[0, 1, 0, 3, 12]<br/>write = 0"] --> b["see 1 at index 1, swap to write<br/>[1, 0, 0, 3, 12]  write = 1"]
  b --> c["see 3 at index 3, swap<br/>[1, 3, 0, 0, 12]  write = 2"]
  c --> d["see 12 at index 4, swap<br/>[1, 3, 12, 0, 0]  write = 3"]
  style d fill:#fed7aa,stroke:#ea580c

The trick

Two pointers moving at different speeds. The read pointer looks at every element. The write pointer only moves when you find something worth keeping. Everything before write is done. Everything between write and read is zeroes.

The steps

1. write = 0.
2. For each index read from 0 to the end:
   • if a[read] is not zero, swap a[write] and a[read], then write += 1.
3. Done. No second pass needed.

def move_zeroes(a):
    write = 0
    for read in range(len(a)):
        if a[read] != 0:
            a[write], a[read] = a[read], a[write]
            write += 1

Time O(n). Space O(1). One pass.

In GPU infrastructure

A drain list is an array of node names, and the ones that have already finished draining are the zeroes. The rollout tool walks the list with a write pointer, keeping every node that still needs work packed at the front in its original order so the maintenance window proceeds in the same sequence the operator planned. The same finger compacts a list of GPUs by dropping the ones an XID error has already taken out, in place, without allocating a second list on a host that is already struggling. The invariant is the thing I check in a code review: everything before write is still pending work.

What I am listening for

• Do you reach for a new array first. That is fine to say, then I ask you to do it in place.
• Can you tell me the invariant: “everything before write is non-zero and in order.” If you can say it, you can prove it.
• The cousin: remove all copies of a given value. Same finger, different test.

Go deeper

• The problem statement: Move Zeroes on LeetCode
• Two-pointer patterns walked through on video: NeetCode on YouTube
• The problem this one grows out of: Two Sum

With AI on the table. The assistant will write this in two seconds. So I ask for a version that counts how many swaps it made and whether the swap of an element with itself should count. Small question, but it tells me whether you read the code the tool gave you.