283. Move Zeroes

Reformulated question¶

Move all 0 values in nums to the end, in-place, while keeping the order of non-zero values unchanged.

Example:

nums = [0,1,0,3,12]  ->  [1,3,12,0,0]

Key trick¶

Use a write pointer:

scan left to right
write each non-zero at the next free position
fill the remaining suffix with zeroes

This is stable and in-place.

Trap¶

Common mistakes:

not preserving the order of non-zero elements
using extra array space
swapping every zero with later values, which may do more writes than needed
forgetting the function must mutate nums and return None

Why is this question interesting?¶

It tests a very common pattern:

two pointers
in-place array compaction
stability under mutation

It also has a small optimization angle: minimize writes.

Solve the problem with idiomatic python¶

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        # write = next position where a non-zero should go
        write = 0

        # compact all non-zero values to the front
        for x in nums:
            if x != 0:
                nums[write] = x
                write += 1

        # fill the rest with zeroes
        for i in range(write, len(nums)):
            nums[i] = 0

A swap-based version also works and can avoid some duplicate writes:

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        write = 0
        for read in range(len(nums)):
            if nums[read] != 0:
                nums[write], nums[read] = nums[read], nums[write]
                write += 1

Pytest test¶

import pytest


@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([0, 1, 0, 3, 12], [1, 3, 12, 0, 0]),
        ([0], [0]),
        ([1], [1]),
        ([1, 2, 3], [1, 2, 3]),
        ([0, 0, 0], [0, 0, 0]),
        ([0, 0, 1], [1, 0, 0]),
        ([1, 0, 2, 0, 3], [1, 2, 3, 0, 0]),
        ([4, 0, 5, 0, 0, 3, 0], [4, 5, 3, 0, 0, 0, 0]),
    ],
)
def test_move_zeroes(nums, expected):
    arr = nums[:]
    Solution().moveZeroes(arr)
    assert arr == expected

Comment my solution¶

Your solution is correct and efficient.

Good points:

in-place
stable
linear time
avoids unnecessary zero writes until needed

Small comment:

count_zeroes works, but write is the more standard interview pointer and is easier to explain
if count_zeroes: is a nice small optimization

Equivalent idea in more common form:

i - count_zeroes is exactly the write index

import pytest

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count_zeroes = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                count_zeroes += 1
            else:
                # shift left non zero numbers
                nums[i - count_zeroes] = nums[i]
                if count_zeroes:
                    nums[i] = 0


@pytest.mark.parametrize(
    ("nums", "expected"),
    [

        ([0,1,0,3,12], [1,3,12,0,0]),
        ([0], [0]),
        ([1,3,12], [1,3,12]),
        ([0,1,0,3,12,0], [1,3,12,0,0,0]),
        ([0,0,1], [1,0,0]),
        ([0,0,1,1], [1,1,0,0]),
        ([0,0,0,0,1,1], [1,1,0,0,0,0]),
        ([0,0,0,0,0,0,1,1,1], [1,1,1,0,0,0,0,0,0])
    ]
)
def test_moveZeroes(nums, expected):
    ns = nums[:]
    Solution().moveZeroes(ns)
    assert ns == expected