LeetCode 283 · Two pointers

Move Zeroes, explained with a picture

Pushing empty slots to the end of a shelf.

Two pointers
▶ Watch it step by step

The problem

Move all 0s to the end of the list while keeping the order of the other numbers, in place.

Input:  [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Picture it

Picture a shelf with books and empty slots (0). A marker w shows where the next book should go. Scan the shelf; every book is slid to w and w moves on. Empty slots naturally end up on the right.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Write pointer for non-zeros, then the rest are zeros. O(n).

Python solution

def move_zeroes(a):
    w = 0
    for r in range(len(a)):
        if a[r] != 0:
            a[w], a[r] = a[r], a[w]
            w += 1
    return a

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.