Move Zeroes Solution Explained

Data Structures / Array

Move Zeroes

Easy

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example

Example 1:

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

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

Explanation: All zeros moved to end, non-zeros keep their relative order.



Example 2:

Input: nums = [0]

Output: [0]

Explanation: Single element array remains unchanged.

Explanation

The key insight is that we need to maintain the relative order of non-zero elements. We can use the two pointers technique - one to track where to place the next non-zero, and one to scan through the array.

The Snowball Approach

Think of zeros as a "snowball" that grows as we encounter more zeros:

Use a pointer insertPos to track where to place the next non-zero
When we find a non-zero, swap it with the element at insertPos
Increment insertPos after each placement

Optimal Approach: Swap or Overwrite?

There are two common implementations:

Swap approach: Swap non-zero elements with position insertPos - maintains zeros in the swapped positions
Overwrite + Fill: First move all non-zeros forward, then fill remaining positions with zeros - slightly cleaner

Step-by-Step Walkthrough

For input [0,1,0,3,12] using swap approach:

Initial: nums = [0, 1, 0, 3, 12], insertPos = 0

i=0: nums[0]=0 → Zero, skip
i=1: nums[1]=1 → Non-zero! Swap with nums[0]
     nums = [1, 0, 0, 3, 12], insertPos = 1

i=2: nums[2]=0 → Zero, skip
i=3: nums[3]=3 → Non-zero! Swap with nums[1]
     nums = [1, 3, 0, 0, 12], insertPos = 2

i=4: nums[4]=12 → Non-zero! Swap with nums[2]
     nums = [1, 3, 12, 0, 0], insertPos = 3

Final: [1, 3, 12, 0, 0] ✓

Idea Map

Start with insertPos = 0

For each element in array:
Is nums[i] non-zero?

Yes: Swap with nums[insertPos], insertPos++

No: Skip (it's a zero)

All zeros are now at the end!

Complexity Analysis

Time Complexity

O(n) - Single pass through the array.

Space Complexity

O(1) - In-place modification using only a pointer variable.

Code


def moveZeroes(nums):
Main function that moves all zeros to the end in-place.

    insert_pos = 0  # Position to place next non-zero
Track where to place the next non-zero element.

    for i in range(len(nums)):
Iterate through the entire array.

        if nums[i] != 0:  # Found a non-zero?
Check if current element is non-zero.

            nums[insert_pos], nums[i] = nums[i], nums[insert_pos]  # Swap
Swap current non-zero with position insert_pos. This moves zeros to the right.

            insert_pos += 1  # Move to next position
Increment insert_pos for next non-zero placement.


public void moveZeroes(int[] nums) {
Main method that moves zeros to end in-place.

    int insertPos = 0;
Position to place next non-zero element.

    for (int i = 0; i < nums.length; i++) {
Iterate through array.

        if (nums[i] != 0) {
Found a non-zero element.

            int temp = nums[insertPos];
Store value at insertPos for swap.

            nums[insertPos] = nums[i];
Place non-zero at insertPos.

            nums[i] = temp;
Complete the swap.

            insertPos++;
Move to next position.

        }
End of if block.

    }
End of for loop.

}
End of method.


void moveZeroes(vector<int>& nums) {
Function takes vector by reference for in-place modification.

    int insertPos = 0;
Track position for next non-zero.

    for (int i = 0; i < nums.size(); i++) {
Iterate through vector.

        if (nums[i] != 0) {
Check if current is non-zero.

            swap(nums[insertPos], nums[i]);
Use STL swap for clean exchange.

            insertPos++;
Increment position.

        }
End of if.

    }
End of for loop.

}
End of function.

Edge Cases & Common Mistakes

⚠️

Must maintain relative order

The problem explicitly requires keeping non-zero elements in their original order. Don't use approaches that change order.

💡

All zeros or all non-zeros

Handle edge cases: array of all zeros (no swaps), or all non-zeros (every element swaps with itself).

✓

Why swap with itself is okay

When insertPos equals i, swapping an element with itself is harmless - no extra check needed.

📝

Minimize operations

The swap approach minimizes write operations. Each non-zero is written at most once.

Understanding Two Pointers

The two pointers technique is a powerful pattern for in-place array manipulation. It allows us to rearrange elements efficiently without extra space.

Learn more about Two Pointers →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Move Zeroes' problem on LeetCode.

AlgoExplained.dev