Move Zeroes

Move every zero to the end while keeping the order of the non-zero values, in place. A write pointer w marks where the next non-zero belongs; the read pointer swaps each non-zero into place.

Traced input: nums = [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]. Original problem: neetcode.io/problems/move-zeroes

Complexity

One pass, in place.

Key idea

• Everything left of w is the non-zero values in their original order.
• When r finds a non-zero, swap it to w and advance w.
• Swapping (instead of overwriting) leaves the zeros behind at the end automatically.

Common mistakes

• Overwriting and then filling zeros works too, but takes two passes.
• Moving zeros by shifting elements is O(n²).
• Swapping when w == r is harmless; don't add special cases for it.

Solution

void moveZeroes(int[] nums) {
    int w = 0;
    for (int r = 0; r < nums.length; r++) {
        if (nums[r] == 0) {
            continue;
        }
        int tmp = nums[w]; nums[w] = nums[r]; nums[r] = tmp;
        w++;
    }
}

def moveZeroes(nums: List[int]) -> None:
    w = 0
    for r in range(len(nums)):
        if nums[r] == 0:
            continue
        nums[w], nums[r] = nums[r], nums[w]
        w += 1

void moveZeroes(vector<int>& nums) {
    int w = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        if (nums[r] == 0) {
            continue;
        }
        swap(nums[w], nums[r]);
        w++;
    }
}

Edge cases

Each one has its own trace in the interactive view.