LeetCode 283 - Move Zeroes

The problem gives us an integer array nums and asks us to move every 0 element to the end of the array while preserving the relative order of all non-zero elements. The phrase "relative order" is extremely important.

leetcodeeasyarraytwo-pointers

LeetCode Problem 283

Difficulty: 🟢 Easy
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem gives us an integer array nums and asks us to move every 0 element to the end of the array while preserving the relative order of all non-zero elements.

The phrase "relative order" is extremely important. It means that if the non-zero numbers originally appear in a certain sequence, they must remain in that same sequence after the operation. For example, in the array [0,1,0,3,12], the non-zero values appear in the order 1, 3, 12. After moving the zeroes, that ordering must still remain unchanged, resulting in [1,3,12,0,0].

Another key requirement is that the operation must be performed in-place. We are not allowed to create another array and return it. Instead, we must directly modify the input array itself.

The constraints tell us that the array length can be as large as 10^4. This is small enough that an O(n^2) solution may technically pass in some environments, but it is inefficient and unnecessary. The problem is designed to encourage an O(n) solution using the two pointers technique.

The values in the array can be negative, positive, or zero. Since only the value 0 matters, the actual magnitude of the numbers is irrelevant.

Several edge cases are important to think about early:

  • An array containing only zeroes, such as [0,0,0]
  • An array containing no zeroes, such as [1,2,3]
  • A single-element array like [0] or [5]
  • Zeroes already at the end, such as [1,2,3,0,0]
  • Zeroes at the beginning or interleaved throughout the array

A naive implementation can easily break the relative ordering requirement or perform unnecessary operations.

Approaches

Brute Force Approach

A straightforward approach is to create a temporary array containing all non-zero elements first, then append all zeroes afterward.

For example:

  • Traverse the array
  • Store every non-zero value into a temporary list
  • Count how many zeroes exist
  • Append that many zeroes to the temporary list
  • Copy everything back into the original array

This works because it explicitly reconstructs the desired ordering. All non-zero elements are preserved in order, and all zeroes are placed at the end.

However, this approach uses extra memory proportional to the size of the array. The problem explicitly asks for an in-place solution, so although this method is easy to understand, it does not fully satisfy the intended optimization requirement.

Optimal Two Pointers Approach

The key insight is that we do not actually need another array. Instead, we can keep track of where the next non-zero element should be placed.

We use a pointer called insert_position that represents the next index where a non-zero number belongs.

As we scan through the array:

  • If the current value is non-zero, we swap it into insert_position
  • Then we increment insert_position
  • If the current value is zero, we simply continue

This works because every non-zero element gets moved forward into the earliest available position, while zeroes naturally drift toward the end.

An additional advantage is that this minimizes unnecessary writes. If the current element is already in the correct position, the swap effectively changes nothing.

Comparison of Approaches

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Uses an extra array to rebuild the result
Optimal O(n) O(1) Uses two pointers and modifies the array in-place

Algorithm Walkthrough

  1. Initialize a pointer called insert_position to 0.

This pointer tracks the index where the next non-zero element should be placed. 2. Traverse the array from left to right using another pointer, usually called current.

The current pointer examines every element exactly once. 3. For each element, check whether it is non-zero.

If the element is zero, we skip it because zeroes belong at the end. 4. If the current element is non-zero, swap it with the value at insert_position.

This places the non-zero value into its correct location near the front of the array. 5. Increment insert_position.

After placing one non-zero element correctly, the next non-zero element should go into the next position. 6. Continue until the entire array has been processed.

By the end:

  • All non-zero elements appear at the beginning in their original order
  • All zeroes have been shifted to the end

Why it works

The invariant maintained throughout the algorithm is:

  • Every index before insert_position contains correctly placed non-zero elements in their original order.
  • Every index from insert_position onward has not yet been finalized.

Whenever we encounter a non-zero element, we place it into the next available correct position. Since we process elements from left to right, their relative order is preserved automatically.

Python Solution

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        insert_position = 0
        
        for current in range(len(nums)):
            if nums[current] != 0:
                nums[insert_position], nums[current] = (
                    nums[current],
                    nums[insert_position]
                )
                insert_position += 1

The implementation begins by initializing insert_position to 0. This variable marks where the next non-zero value should be written.

The loop iterates through every index in the array using current.

Whenever a non-zero value is found, it is swapped into the correct front position. This ensures that all non-zero elements are compacted toward the beginning of the array.

After the swap, insert_position is incremented because one more non-zero element has been placed correctly.

If the current value is zero, the algorithm does nothing and continues scanning.

By the time the traversal completes, all non-zero elements have been shifted forward in order, and all zeroes occupy the remaining positions at the end.

Go Solution

func moveZeroes(nums []int) {
    insertPosition := 0

    for current := 0; current < len(nums); current++ {
        if nums[current] != 0 {
            nums[insertPosition], nums[current] =
                nums[current], nums[insertPosition]

            insertPosition++
        }
    }
}

The Go implementation follows exactly the same logic as the Python version.

One notable difference is that Go uses slices instead of Python lists. Since slices are reference-like structures, modifications inside the function directly affect the original array passed by the caller.

There are no integer overflow concerns in this problem because we are only comparing and swapping values, not performing arithmetic operations on them.

Go also naturally handles empty or nil slices safely in this loop structure, although the constraints guarantee at least one element.

Worked Examples

Example 1

Input:

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

Initial state:

Current Index Current Value Insert Position Array State
Start - 0 [0,1,0,3,12]

Step-by-step execution:

Current Index Current Value Action Insert Position After Array State
0 0 Skip 0 [0,1,0,3,12]
1 1 Swap with index 0 1 [1,0,0,3,12]
2 0 Skip 1 [1,0,0,3,12]
3 3 Swap with index 1 2 [1,3,0,0,12]
4 12 Swap with index 2 3 [1,3,12,0,0]

Final output:

[1,3,12,0,0]

Example 2

Input:

nums = [0]

Initial state:

Current Index Current Value Insert Position Array State
Start - 0 [0]

Step-by-step execution:

Current Index Current Value Action Insert Position After Array State
0 0 Skip 0 [0]

Final output:

[0]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is visited exactly once
Space O(1) Only a few extra variables are used

The algorithm performs a single linear scan through the array, so the runtime grows proportionally with the input size.

The space complexity is constant because no additional data structures proportional to the input size are allocated. All modifications happen directly inside the original array.

Test Cases

from typing import List

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

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

solution = Solution()

nums = [0, 1, 0, 3, 12]
solution.moveZeroes(nums)
assert nums == [1, 3, 12, 0, 0]  # standard mixed case

nums = [0]
solution.moveZeroes(nums)
assert nums == [0]  # single zero element

nums = [1]
solution.moveZeroes(nums)
assert nums == [1]  # single non-zero element

nums = [1, 2, 3]
solution.moveZeroes(nums)
assert nums == [1, 2, 3]  # no zeroes present

nums = [0, 0, 0]
solution.moveZeroes(nums)
assert nums == [0, 0, 0]  # all zeroes

nums = [1, 0, 2, 0, 3, 0]
solution.moveZeroes(nums)
assert nums == [1, 2, 3, 0, 0, 0]  # alternating zeroes

nums = [0, 0, 1, 2]
solution.moveZeroes(nums)
assert nums == [1, 2, 0, 0]  # leading zeroes

nums = [1, 2, 0, 0]
solution.moveZeroes(nums)
assert nums == [1, 2, 0, 0]  # trailing zeroes already correct

nums = [-1, 0, -2, 3]
solution.moveZeroes(nums)
assert nums == [-1, -2, 3, 0]  # negative numbers included

Test Case Summary

Test Why
[0,1,0,3,12] Standard mixed example
[0] Smallest zero-only input
[1] Smallest non-zero input
[1,2,3] No zeroes present
[0,0,0] All elements are zero
[1,0,2,0,3,0] Multiple interleaved zeroes
[0,0,1,2] Leading zeroes
[1,2,0,0] Zeroes already at the end
[-1,0,-2,3] Handles negative values correctly

Edge Cases

One important edge case is an array containing only zeroes, such as [0,0,0]. A buggy implementation might accidentally overwrite values or move pointers incorrectly when no non-zero elements exist. In this implementation, the insert_position pointer never advances because no non-zero elements are encountered. The array remains unchanged, which is the correct behavior.

Another important case is an array with no zeroes at all, such as [1,2,3]. Some implementations may perform unnecessary shifting operations or accidentally alter the ordering. Here, each element swaps with itself because insert_position and current are always equal. This preserves the array exactly as it was.

A third edge case is when zeroes appear at the beginning of the array, such as [0,0,1,2]. Naive approaches sometimes fail to preserve ordering while compacting non-zero values forward. This implementation processes elements from left to right, ensuring that 1 is placed before 2, preserving the original relative order.

Another subtle case is arrays containing negative numbers, such as [-1,0,-2,3]. Since the algorithm only checks whether a value equals zero, all non-zero values, regardless of sign, are handled uniformly and correctly preserved.