VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.5 of 16 in this moduleFree

Move Zeroes

Move every zero to the end while keeping the other values in order, in place: from a copy-based brute force to a read/write pointer pass, then fewer writes when writes are expensive, and what changes if order doesn't matter or you're filtering padding out of a batch.

about 10 min 6 Python examples 2 quick checks

Problem. Given a list nums, move all zeros to the end in place, keeping the relative order of the non-zero values.

text
[0, 1, 0, 3, 12]   →   [1, 3, 12, 0, 0]

ML context. This is stable partitioning, the operation behind compacting a batch: move real tokens to the front and padding to the back, keep valid detections ahead of suppressed ones, or pack non-empty rows of a sparse buffer together without reordering them.

It's an "Easy" problem that teaches a pattern used everywhere in this roadmap: a read pointer that visits every element and a write pointer that marks where the next kept element goes.


1. Step 1: Clarify

Question Answer Why it matters
Must the non-zero order be kept? Yes Rules out swapping zeros with the end
In place? Yes, O(1) extra Rules out building a new list (as the final answer)
Values other than zero? Any integers Only == 0 matters
n? Up to 10⁴ (or 10⁶) Rules out shifting elements repeatedly

2. Step 2: Brute force

Two natural brute forces, with different costs.

Brute force A: remove zeros and append them. list.remove(0) shifts everything after it; doing it z times costs O(n · z).

python
def move_zeroes_remove(nums):
    zeros = nums.count(0)
    for _ in range(zeros):
        nums.remove(0)          # O(n): finds the first 0 and shifts the rest left
        nums.append(0)


nums = [0, 1, 0, 3, 12]
move_zeroes_remove(nums)
assert nums == [1, 3, 12, 0, 0]
print("remove-and-append works: O(n·z) time")

Brute force B: build a copy. Collect non-zeros, pad with zeros, copy back. O(n) time, but O(n) extra space, which breaks the in-place constraint.

python
def move_zeroes_copy(nums):
    kept = [x for x in nums if x != 0]
    nums[:] = kept + [0] * (len(nums) - len(kept))     # O(n) extra memory


nums = [0, 1, 0, 3, 12]
move_zeroes_copy(nums)
assert nums == [1, 3, 12, 0, 0]
print("copy version works: O(n) time, O(n) extra space")

So brute force A is in place but slow when there are many zeros (all zeros: O(n²)); brute force B is fast but uses memory. The optimisation must get both: O(n) time and O(1) space.


3. Step 3: Optimise: a read pointer and a write pointer

Look at what the copy did: it walked the list once and wrote each non-zero to the next free slot of a new list. We can do the same writes into the same list: the write position never gets ahead of the read position, so we never overwrite a value we haven't read yet.

frames over [0, 1, 0, 3, 12]; the read pointer scans every element and each non-zero is written at the write pointer, which then advances; finally positions 3 and 4 are filled with zeros.
Diagram— frames over [0, 1, 0, 3, 12]; the read pointer scans every element and each non-zero is written at the write pointer, which then advances; finally positions 3 and 4 are filled with zeros.
python
import random


def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]      # write <= read, so nothing unread is lost
            write += 1
    for i in range(write, len(nums)):     # everything after the kept values becomes 0
        nums[i] = 0


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


for case in ([], [0], [1], [0, 0, 1], [1, 2, 3], [0, 1, 0, 3, 12], [4, 0, 5, 0, 0, 6]):
    nums = list(case)
    move_zeroes(nums)
    assert nums == reference(case), case
rng = random.Random(11)
for _ in range(500):
    case = [rng.choice([0, 0, rng.randint(-5, 5)]) for _ in range(rng.randint(0, 20))]
    nums = list(case)
    move_zeroes(nums)
    assert nums == reference(case)
print("read/write pointers: O(n) time, O(1) space, order kept")
  • Time: one read pass plus filling the tail: O(n).
  • Space: O(1).
  • Invariant (say it out loud): "everything before write is the non-zero values seen so far, in order." Each step keeps it true; when read reaches the end, the invariant is the answer.

Quick check

Why can't the write pointer overwrite a value that hasn't been read yet?

  1. Python prevents it
  2. write only advances when a non-zero is read, so write ≤ read at all times; it only ever writes into positions already read
  3. The list is copied first
  4. Zeros are skipped
Show the answer

B. write only advances when a non-zero is read, so write ≤ read at all times; it only ever writes into positions already read — Maintaining write ≤ read is what makes the in-place version safe.


4. When writes are expensive: swap only when needed

The version above writes every non-zero value, even the ones already in the right place. In an array of a million values with ten zeros near the end, it does about a million writes to move about ten things.

A variant swaps the non-zero into the write slot only when they differ. Values already in place aren't rewritten. Swapping (rather than overwriting) also means there's no tail-filling pass: the zeros travel backwards naturally.

python
import random


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


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


rng = random.Random(12)
for _ in range(500):
    case = [rng.choice([0, rng.randint(1, 9)]) for _ in range(rng.randint(0, 20))]
    nums = list(case)
    move_zeroes_swap(nums)
    assert nums == reference(case)

late_zeros = list(range(1, 1_000_001))
for i in range(-20, -10):
    late_zeros[i] = 0                                       # ten zeros, followed by ten more values
writes = move_zeroes_swap(late_zeros)
print("writes with zeros near the end:", writes)            # 10 swaps of 2 writes each
assert writes == 20
assert move_zeroes_swap([0] + list(range(1, 11))) == 20     # a zero first: every value moves
for a million values with ten zeros, building a new list writes about 2 × 10⁶ times, write-forward about 10⁶, and swap-only-if-needed about 20 when the zeros are near the end (up to 2n when a zero comes first).
Chart— for a million values with ten zeros, building a new list writes about 2 × 10⁶ times, write-forward about 10⁶, and swap-only-if-needed about 20 when the zeros are near the end (up to 2n when a zero comes first).

Both versions are O(n) time and O(1) space. The difference is the constant: which matters only when the constraint says writes are costly (flash storage, memory shared across processes, very large records). Name the trade-off; don't overclaim it: with a zero at the front, the swap version moves everything too.


5. When the constraints change

If the constraint becomes… Best approach Time Extra space Note
Order must be kept (classic) Read/write pointers O(n) O(1)
Writes are expensive Swap only when read ≠ write O(n) O(1) fewer writes when zeros are late
Order doesn't matter Swap each zero with the last non-zero O(n) O(1) at most z swaps
Must not modify the input Build a filtered copy O(n) O(n)
Keep only values passing any test (not just ≠ 0) Same read/write pass with a predicate O(n) O(1) stable filter
NumPy array, speed matters Boolean mask: x[x != 0] + zeros O(n), vectorised O(n)

The order-doesn't-matter row shows how a relaxed constraint enables a cheaper method: walk two pointers inward and swap each zero on the left with a non-zero on the right. That does at most one swap per zero, but scrambles the order, so it's only allowed when order doesn't matter.

python
import random


def move_zeroes_unordered(nums):
    """Zeros to the end; the order of non-zeros is NOT preserved."""
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left] != 0:
            left += 1
        elif nums[right] == 0:
            right -= 1
        else:
            nums[left], nums[right] = nums[right], nums[left]   # one swap fixes one zero


rng = random.Random(13)
for _ in range(500):
    case = [rng.choice([0, rng.randint(1, 9)]) for _ in range(rng.randint(0, 20))]
    nums = list(case)
    move_zeroes_unordered(nums)
    nz = sum(1 for x in case if x != 0)
    assert sorted(nums[:nz]) == sorted(x for x in case if x != 0)   # same values, any order
    assert all(x == 0 for x in nums[nz:])
print("unordered version works with at most one swap per zero")

The general tool: a stable filter in place

The read/write pass isn't really about zeros: it keeps the elements that pass a test, in order. That's how you'd compact padding out of a token batch, or keep only detections above a score threshold:

python
def filter_in_place(items, keep):
    write = 0
    for x in items:
        if keep(x):
            items[write] = x
            write += 1
    del items[write:]                    # drop the tail instead of zero-filling it
    return items


PAD = 0
tokens = [101, 7592, PAD, 2088, PAD, PAD, 102]
assert filter_in_place(tokens, lambda t: t != PAD) == [101, 7592, 2088, 102]

detections = [("cat", 0.91), ("dog", 0.12), ("car", 0.66), ("cup", 0.05)]
assert filter_in_place(detections, lambda d: d[1] >= 0.5) == [("cat", 0.91), ("car", 0.66)]
print("stable in-place filter works for any test")

Quick check

The interviewer says the order of non-zero values doesn't matter. What changes?

  1. You can swap each zero with a non-zero from the end, doing at most one swap per zero, instead of shifting every non-zero forward; still O(n) time and O(1) space, but fewer writes
  2. Nothing
  3. You must sort the list
  4. You must use extra memory
Show the answer

A. You can swap each zero with a non-zero from the end, doing at most one swap per zero, instead of shifting every non-zero forward; still O(n) time and O(1) space, but fewer writes — Relaxing the stability constraint unlocks a cheaper partition with at most z swaps.


6. Saying it out loud

"Removing zeros one by one shifts the list each time: O(n·z), up to O(n²). Building a filtered copy is O(n) but uses O(n) memory. Instead I'll keep a write pointer: every non-zero is written to the next slot, which never gets ahead of the read pointer, then I fill the rest with zeros. O(n) time, O(1) space, order preserved. If writes were expensive I'd swap only when read ≠ write; if order didn't matter I'd swap zeros with non-zeros from the end."


Check yourself

  1. What are the costs of the two brute forces, and which constraint does each violate?
  2. What is the invariant of the read/write pass?
  3. Why is it safe to write into the same list you're reading?
  4. When does the swap-only-if-needed variant save writes, and when doesn't it?
  5. What does "order doesn't matter" unlock?
  6. How does the same pass compact padding tokens out of a batch?
Answers
  1. Remove-and-append: O(n·z) time, too slow with many zeros. Copy: O(n) time but O(n) extra space, breaking "in place".
  2. Everything before write is the non-zero values seen so far, in their original order.
  3. write only advances after reading a non-zero, so write ≤ read: it never overwrites an unread value.
  4. When the zeros are near the end, values before the first zero are never rewritten. With a zero at the front, every value moves anyway.
  5. Swapping each zero with a non-zero from the end: at most one swap per zero, but the order of non-zeros changes.
  6. Use the predicate "token isn't padding", write kept tokens forward, and truncate the tail.