033. Move Zeros Stably

Why this mechanism works

First compact accepted values into a prefix. Because write never exceeds the read position, each write is safe. After all original values have been read, every remaining position can be filled with zero. The second phase avoids swapping zeros repeatedly through the list.

State and boundaries

write is the count of nonzero values consumed; nums[:write] is their stable sequence.

Protocol

1. Scan original values.
2. Write each nonzero at write and advance write.
3. After the scan fill the remaining suffix with zeros.
4. Return nums.

Visualization

[0,1,0,3,12]
compact: [1,3,12 | ?,?]
fill:    [1,3,12 | 0,0]

Python implementation

def move_zeros(nums):
    write = 0
    for value in nums:
        if value != 0:
            nums[write] = value
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0
    return nums

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 move_zeros: write = 0
nums=[0, 1, 0, 3, 12]; write=0

L3 move_zeros: for value in nums:
nums=[0, 1, 0, 3, 12]; write=0; value=0

L3 move_zeros: for value in nums:
nums=[0, 1, 0, 3, 12]; write=0; value=1

L5 move_zeros: nums[write] = value
nums=[1, 1, 0, 3, 12]; write=0; value=1

L6 move_zeros: write += 1
nums=[1, 1, 0, 3, 12]; write=1; value=1

L3 move_zeros: for value in nums:
nums=[1, 1, 0, 3, 12]; write=1; value=0

L3 move_zeros: for value in nums:
nums=[1, 1, 0, 3, 12]; write=1; value=3

L5 move_zeros: nums[write] = value
nums=[1, 3, 0, 3, 12]; write=1; value=3

... 4 intermediate state changes omitted ...

L7 move_zeros: for i in range(write, len(nums)):
nums=[1, 3, 12, 3, 12]; write=3; value=12; i=3

L8 move_zeros: nums[i] = 0
nums=[1, 3, 12, 0, 12]; write=3; value=12; i=3

L7 move_zeros: for i in range(write, len(nums)):
nums=[1, 3, 12, 0, 12]; write=3; value=12; i=4

L8 move_zeros: nums[i] = 0
nums=[1, 3, 12, 0, 0]; write=3; value=12; i=4

L2 move_zeros: write = 0
nums=[]; write=0

Why the solution is correct

The first phase appends nonzero values in encounter order without overwriting unread data. The number of unwritten positions equals the number of zeros. Filling exactly that suffix preserves length and multiplicity.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Swapping arbitrary nonzero endpoints can break stability. Filling zeros during the read scan can overwrite values not yet examined.

Reasoning card

Transfer exercise

Generalize zero to a discard predicate and state whether the discarded suffix must preserve order too.