Move Zeroes

You'll move values inside one list with two pointers: one reads, one writes. You need list assignment and indexes. Related chapter: two pointers.

1. The problem

You get a list of integers. Move every zero to the end, and keep the other numbers in their original order. Change the list itself: don't build a second list, and return None. This is LeetCode 283. Our function also handles an empty list.

"Keep their order" is the phrase that matters. Sorting would move the zeros, but it would also reorder everything else.

2. A correct baseline

def baseline(nums):
    zeros=0
    i=0
    while i<len(nums)-zeros:
        if nums[i]==0:
            nums.pop(i)
            nums.append(0)
            zeros+=1
        else:
            i+=1

a=[0,3,0,1,4]; baseline(a); assert a==[3,1,4,0,0]
a=[0,0]; baseline(a); assert a==[0,0]
a=[2,-1,3]; baseline(a); assert a==[2,-1,3]

Each pop(i) shifts every later number one place left. So this takes O(n²) time in the worst case: the work grows with the square of the list's length. On 100,000 numbers that are half zeros, that's over a billion shifts. It uses O(1) extra space.

The bottleneck. Every zero we remove shifts the rest of the list, so the same numbers move again and again.

3. The observation

Look at the answer for [0, 3, 0, 1, 4]: it's [3, 1, 4, 0, 0]. The front holds the nonzeros in order, and the rest is zeros. So you don't need to move the zeros at all. Copy each nonzero to the next free spot at the front, then fill the rest with zeros.

Use two indexes. read visits every number. write marks the next free spot at the front. Each number moves at most once. This works because write never gets ahead of read, so we only overwrite numbers we've already read.

4. The solution and a trace

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        """Modify nums in place, preserving nonzero order and list length."""
        write=0
        for read in range(len(nums)):
            if nums[read]!=0:
                nums[write]=nums[read]
                write+=1
        while write<len(nums):
            nums[write]=0
            write+=1

solve=Solution().moveZeroes
for before,after in [([0,3,0,1,4],[3,1,4,0,0]),([0,0],[0,0]),([2,-1,3],[2,-1,3]),([],[])]:
    nums=before.copy(); alias=nums
    assert solve(nums) is None
    assert nums==after and alias is nums

Trace [0,3,0,1,4]. The repeated values in the middle rows are leftovers that get overwritten later.

5. Why it works

What stays true. Before each read, nums[:write] holds the nonzeros read so far, in order.

Nothing gets lost. write never passes read, so writing never overwrites a number we haven't read yet.

The result is right. When reading ends, the first write spots hold all the nonzeros in order. Filling the rest with zeros gives exactly the answer, with the same length.

6. Cost, edge cases, and failure

Cost. One pass to read and one to fill: O(n) time, growing in step with the list. O(1) extra space.

Edge cases. Empty and all-zero lists need no special handling. The duplicated values in the middle of the run are harmless, because the fill overwrites them. Assigning a new list to nums wouldn't change the caller's list, so the function must write into the existing one.

Where it fails. Sorting puts the zeros last but also reorders the other numbers:

nums=[0,2,1]
wrong=sorted(nums,reverse=True)  # Deliberately wrong: sorts nonzeros too.
solve(nums)
assert wrong==[2,1,0]
nums=[0,1,2]; wrong=sorted(nums,reverse=True); solve(nums)
assert nums==[1,2,0] and wrong!=nums

import random
rng=random.Random(283)
for _ in range(1000):
    original=[rng.choice([-2,-1,0,0,1,2]) for _ in range(rng.randrange(45))]
    actual=original.copy(); expected=original.copy()
    baseline(expected); alias=actual
    assert solve(actual) is None
    assert actual==expected and alias is actual and len(actual)==len(original)