DSA Move Zeroes

The problem

Move Zeroes compacts the non-zero values of a list to the front. Zeros fill the cells that remain at the back. The non-zero values keep their original order.

The change happens in place. The same list holds the result, and no second list is built.

cases = [
    ([0, 1, 0, 3, 12], [1, 3, 12, 0, 0]),
    ([0, 3, 0, 5, 2], [3, 5, 2, 0, 0]),
    ([1, 2, 3], [1, 2, 3]),
    ([0, 0, 0], [0, 0, 0]),
]
for values, expected in cases:
    print(values, '->', expected)

Intuition

The first idea builds two groups. Collect the non-zero values in order. Count the zeros and append that many at the end.

That idea is correct. It also builds a second list of the same size. The in-place version must reach the same order without that copy.

values = [0, 3, 0, 5, 2]
result = []
for value in values:
    if value != 0:
        result.append(value)
while len(result) < len(values):
    result.append(0)
print('new list:', result)
print('original:', values)

Brute force

A slow in-place method bubbles each non-zero value left. It swaps a value past every zero before it. One pair swaps at a time.

def move_zeroes_brute(values):
    swaps = 0
    for read in range(len(values)):
        index = read
        while index > 0 and values[index - 1] == 0 and values[index] != 0:
            values[index - 1], values[index] = values[index], values[index - 1]
            swaps += 1
            index -= 1
    return values, swaps

for values in [[0, 1, 0, 3, 12], [0, 0, 0, 4], [0, 3, 0, 5, 2]]:
    result, swaps = move_zeroes_brute(list(values))
    print(values, '->', result, 'swaps:', swaps)

A value at the back can swap many times. The swap count grows with the distance each value travels. A single copying pass can settle each value once.

The optimal solution: one write index

The key idea is a write index. The write index marks the next free slot at the front, and each non-zero value found is copied there once.

def move_zeroes(values):
    write = 0
    for read in range(len(values)):
        if values[read] != 0:
            values[write] = values[read]
            write += 1
    while write < len(values):
        values[write] = 0
        write += 1
    return values

cases = [[0, 1, 0, 3, 12], [0, 3, 0, 5, 2], [1, 2, 3], [0, 0, 0]]
for values in cases:
    print(values, '->', move_zeroes(list(values)))

Walkthrough

Take the list [0, 3, 0, 5, 2]. The read index visits every cell. The write index advances only on a non-zero value.

values = [0, 3, 0, 5, 2]
write = 0
for read in range(len(values)):
    if values[read] != 0:
        values[write] = values[read]
        write += 1
    print('read', read, 'write next', write, 'list:', values)
while write < len(values):
    values[write] = 0
    write += 1
print('after the fill:', values)

The first pass packs 3, 5 and 2 at the front. Stale copies remain in the tail after that pass. The fill loop overwrites the tail with zeros.

Complexity

Time is O(n). The read index visits each cell once, and the fill loop visits each tail cell once.

Space is O(1). Two indices are the only extra storage.

def visits(n):
    values = [0, 1] * (n // 2)
    count = 0
    write = 0
    for read in range(len(values)):
        count += 1
        if values[read] != 0:
            values[write] = values[read]
            write += 1
    while write < len(values):
        count += 1
        values[write] = 0
        write += 1
    return count

for n in [8, 16, 32]:
    print('n =', n, 'visits:', visits(n))

Edge cases and pitfalls

A list with no zeros passes through unchanged. Each value copies onto itself, and that copy is harmless. The fill loop then never runs.

Sorting the list is a tempting shortcut. Sorting also moves the zeros to the back in some arrangements and to the front in others. Sorting also reorders the non-zero values, and this problem requires their order to survive.

def move_zeroes(values):
    write = 0
    for read in range(len(values)):
        if values[read] != 0:
            values[write] = values[read]
            write += 1
    while write < len(values):
        values[write] = 0
        write += 1
    return values

print('empty:', move_zeroes([]))
print('no zeros:', move_zeroes([1, 2, 3]))
print('all zeros:', move_zeroes([0, 0, 0]))
print('zeros at back:', move_zeroes([4, 5, 0, 0]))
print('order kept:', move_zeroes([0, 9, 0, 1, 0, 7]))