LeetCode 283: Move Zeroes

Problem Restatement

We are given an integer array nums.

We need to move all zeroes to the end of the array while keeping the relative order of all non-zero elements unchanged.

The operation must be done in-place.

For example:

[0, 1, 0, 3, 12]

should become:

[1, 3, 12, 0, 0]

The order of:

1, 3, 12

must stay the same.

The official statement requires an in-place solution and encourages minimizing the total number of operations. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        ...

Examples

For:

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

The result should be:

[1, 3, 12, 0, 0]

For:

nums = [0]

The result stays:

[0]

For:

nums = [1, 2, 3]

There are no zeroes, so the array remains:

[1, 2, 3]

First Thought: Build Another Array

A direct solution is:

1. Collect all non-zero values.
2. Count how many zeroes exist.
3. Append that many zeroes at the end.
4. Copy everything back.

Example:

[0, 1, 0, 3, 12]

Non-zero values:

[1, 3, 12]

Zero count:

2

Final array:

[1, 3, 12, 0, 0]

Code:

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        values = []

        for num in nums:
            if num != 0:
                values.append(num)

        zeroes = len(nums) - len(values)

        values.extend([0] * zeroes)

        for i in range(len(nums)):
            nums[i] = values[i]

This works, but it uses extra memory.

The problem asks for an in-place solution.

Key Insight

We only need to track where the next non-zero value should go.

Use two pointers:

As we scan left to right:

• If nums[i] is non-zero, place it at nums[write].
• Then advance write.

After all non-zero values are moved forward, every remaining position becomes zero.

Algorithm

Initialize:

write = 0

First pass:

Scan the array from left to right.

Whenever we see a non-zero value:

nums[i] != 0

write it into:

nums[write]

Then increment write.

After this pass, all non-zero values appear at the front in the correct order.

Second pass:

Fill the remaining positions with zeroes.

while write < len(nums):
    nums[write] = 0
    write += 1

Correctness

During the first pass, write always points to the first position where the next non-zero value should be placed.

Whenever the algorithm sees a non-zero value, it copies that value into nums[write] and increments write.

Because the scan proceeds from left to right, non-zero values are written in exactly the same order they originally appeared. Therefore relative order is preserved.

After the first pass:

• Positions before write contain all non-zero values in correct order.
• Positions from write onward are irrelevant temporary values.

The second pass fills every remaining position with zero.

So after completion:

1. All non-zero values appear first.
2. Their original order is preserved.
3. All remaining positions contain zero.

Therefore the final array satisfies the problem requirements.

Complexity

Implementation

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        write = 0

        for i in range(len(nums)):
            if nums[i] != 0:
                nums[write] = nums[i]
                write += 1

        while write < len(nums):
            nums[write] = 0
            write += 1

Code Explanation

We start with:

write = 0

This is where the next non-zero value should go.

Then we scan every element:

for i in range(len(nums)):

If the current value is non-zero:

if nums[i] != 0:

we move it forward:

nums[write] = nums[i]

and advance the write position:

write += 1

After the loop, all non-zero values are packed at the front.

The remaining positions should become zero:

while write < len(nums):
    nums[write] = 0
    write += 1

The function returns nothing because the array is modified in-place.

Alternative Swap Version

Another common implementation swaps elements immediately.

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        write = 0

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

This version may perform fewer writes in some cases.

Example:

[0, 1, 0, 3, 12]

Process:

swap 1 with 0
swap 3 with 0
swap 12 with 0

Result:

[1, 3, 12, 0, 0]

Testing

def test_move_zeroes():
    s = Solution()

    nums = [0, 1, 0, 3, 12]
    s.moveZeroes(nums)
    assert nums == [1, 3, 12, 0, 0]

    nums = [0]
    s.moveZeroes(nums)
    assert nums == [0]

    nums = [1, 2, 3]
    s.moveZeroes(nums)
    assert nums == [1, 2, 3]

    nums = [0, 0, 0]
    s.moveZeroes(nums)
    assert nums == [0, 0, 0]

    nums = [4, 0, 5, 0, 0, 3]
    s.moveZeroes(nums)
    assert nums == [4, 5, 3, 0, 0, 0]

    print("all tests passed")

test_move_zeroes()

Test meaning: