Move Zeroes: Two Pointers, One Pass, Order Preserved

"Move all the zeroes to the end, keep the other numbers in order, and do it in place." Move Zeroes is a warm-up, but it is also the smallest clean example of the read pointer and write pointer pattern that sits under removing duplicates, removing an element, and partitioning in general. The interviewer is checking three things: that you do not reach for a second array, that you do not delete from the middle of a list, and that you can say why the order survives.

The problem it solves

Given [0, 4, 0, 9, 2, 0, 7], produce [4, 9, 2, 7, 0, 0, 0] in the same list. The non-zero values must stay in the order they arrived; the zeroes just have to end up at the back.

The two obvious answers are both wrong. Building [x for x in nums if x] + zeros is linear, but it allocates a second array, which the in-place constraint rules out. Calling pop on every zero and appending it stays in place, but every pop from the middle shifts everything after it one slot left. On an array whose first half is zeroes that is quadratic: almost fifty million shifts for ten thousand elements.

The intuition

Split the array into two regions with a single index, write. Everything to the left of write is finished: non-zero values, in their original order. Everything from write onwards is not yet decided.

A second index, read, walks the whole array once. When it finds a zero, it does nothing; the zero stays behind, to be covered or pushed back later. When it finds a non-zero, that value belongs at write, so it goes there and write moves up one.

Why is the order safe? read visits the non-zero values left to right, and each one is placed at the next free slot of the finished region, also left to right. The first non-zero seen goes to slot 0, the second to slot 1, and so on. Nothing ever overtakes anything. And because write never passes read, a value is never overwritten before it has been read.

There are two ways to finish. The copy version copies each non-zero forward, then fills every slot from write to the end with zero. The swap version exchanges nums[write] and nums[read] instead, so the zeroes are carried back as the non-zeroes move forward, and nothing needs filling at the end. The swap version also skips the write entirely when read == write, which is the follow-up interviewers ask about: an array with no zeroes at all is left untouched.

Watch it run

The animation uses [0, 4, 0, 9, 2, 0, 7]. The write pointer marks the next slot that should hold a non-zero; the read pointer scans everything. At index 0 it meets a zero: skip it, and leave write where it is. At index 1, 4 is non-zero and belongs at index 0, so it is moved forward, order preserved, and write advances to 1. Another zero at index 2 is skipped. Then 9 belongs at index 1, and 2 belongs at index 2, each move pushing write up by one. The zero at index 5 is skipped, and 7 goes to index 3. The closing frame states the result: one pass, no second array, the non-zeroes keep their order and every zero has been pushed to the tail.

The code

The copy version, as in the lesson, on the animation's input, plus the small cases that break careless loops:

def move_zeroes(nums):
    write = 0                              # next slot for a non-zero
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]       # copy forward, order kept
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0                        # pad the tail
    return nums

print(move_zeroes([0, 4, 0, 9, 2, 0, 7]))  # [4, 9, 2, 7, 0, 0, 0]
print(move_zeroes([1, 2, 3]), move_zeroes([0, 0]), move_zeroes([]))
# [1, 2, 3] [0, 0] []

The swap version, which is what the animation draws. It counts writes: on an array with a single zero at the very end, the copy version still writes every slot, while the swap version writes nothing at all:

def move_zeroes_swap(nums):
    write, writes = 0, 0
    for read in range(len(nums)):
        if nums[read] != 0:
            if read != write:              # already in place: touch nothing
                nums[write], nums[read] = nums[read], nums[write]
                writes += 2
            write += 1
    return nums, writes

print(move_zeroes_swap([0, 4, 0, 9, 2, 0, 7]))       # ([4, 9, 2, 7, 0, 0, 0], 8)
mostly_full = [5, 3, 8, 1, 9, 2, 7, 0]
print(move_zeroes_swap(mostly_full[:])[1], len(mostly_full))   # 0 8

The approach to avoid, with its cost counted. Every pop from the middle shifts the rest of the list:

def move_zeroes_naive(nums):
    shifted, i = 0, 0
    for _ in range(len(nums)):             # one decision per original element
        if nums[i] == 0:
            shifted += len(nums) - i - 1   # pop(i) moves everything after i
            nums.pop(i)
            nums.append(0)
        else:
            i += 1
    return nums, shifted

print(move_zeroes_naive([0, 4, 0, 9, 2, 0, 7]))      # ([4, 9, 2, 7, 0, 0, 0], 14)
print(move_zeroes_naive([0] * 5_000 + [1] * 5_000)[1])   # 49995000

One warning about generalising. Swapping keeps the front in order, but the values carried to the back can come out shuffled. With zeroes that is invisible, since all zeroes look alike. Move negatives to the back instead and it shows; a stable sort on a boolean key keeps both groups in order, at O(n log n):

def move_to_back_swap(nums, junk):
    write = 0
    for read in range(len(nums)):
        if not junk(nums[read]):
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

print(move_to_back_swap([-1, 2, -3, 4], lambda x: x < 0))   # [2, 4, -3, -1]
print(sorted([-1, 2, -3, 4], key=lambda x: x < 0))          # [2, 4, -1, -3]

Checked against a filter-and-pad reference on 2,000 seeded random arrays, many of them zero-heavy, empty or single-element:

import random

def reference(nums):
    kept = [x for x in nums if x != 0]
    return kept + [0] * (len(nums) - len(kept))

random.seed(25)
ok = True
for _ in range(2_000):
    a = [random.choice([0, 0, random.randint(-9, 9)]) for _ in range(random.randint(0, 12))]
    want = reference(a)
    ok &= move_zeroes(a[:]) == want
    ok &= move_zeroes_swap(a[:])[0] == want
    ok &= move_zeroes_naive(a[:])[0] == want
    ok &= move_to_back_swap(a[:], lambda x: x == 0) == want
print(ok)                                  # True

The complexity

• Time: O(n). read visits each element once; the copy version's padding loop touches at most n more slots.
• Space: O(1). Two integers, no second array.
• Writes: the copy version always writes n slots; the swap version writes only when a non-zero has to move.
• The pop-and-append version: O(n²) in the worst case, because each pop from the middle is O(n).

Where it goes wrong

• Forgetting to pad. The copy version leaves stale values between write and the end unless you zero them.
• Swapping when read == write. Harmless for the answer, but it is exactly the redundant write the follow-up asks you to remove.
• Deleting while iterating. Removing from a list inside a for loop over it skips the element after each removal.
• Assuming the swap version is fully stable. It is stable for the kept values only. Fine for zeroes, wrong for a general "move these to the back, in order".
• Returning a new list. The problem says in place; a comprehension is a different answer.

When it shows up in interviews

Move Zeroes is usually an opener, and the follow-up is the real question: minimise the number of writes. The same write-pointer loop answers "remove element", "remove duplicates from a sorted array" and "compact this buffer", and it is the one-colour version of the three-way partition in Dutch national flag. It sits in the two-pointer family alongside the pairs in the two-pointers technique, and the patterns cheat sheet files it with the other same-direction pointer problems.

How to say it in an interview

"I keep a write index for the next slot that should hold a non-zero, and a read index that scans the array once. Each non-zero I read goes to the write slot and the write index moves up; zeroes are skipped. Non-zeroes are placed in the order they are read, so their order is preserved, and write never passes read, so nothing is overwritten before it is read. Then I fill the rest with zeroes. That is O(n) time and O(1) space. If writes matter, I swap instead of copying and skip the swap when both indexes are equal, so an array that is already correct is never written."