Move Zeroes

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Related Problems
Key Takeaways

📋 Problem Statement

Given an integer array nums, move all zeros to the end without changing the relative order of non-zero elements.

You must modify the array directly and avoid creating another full-size array as the main solution.

Examples

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

Example 2:
Input: [0,0,1]
Output: [1,0,0]

🎯 Real-World Analogy

Airport Security Line Reordering

Imagine people with valid boarding passes (non-zero) and people missing documents (zero). You keep a marker for the next open valid spot. As you scan left to right, each valid traveler moves to the marker spot, then the marker advances.

Invalid travelers naturally drift to the back because valid travelers keep filling the front first.

💡 Key Insights

Maintain a write pointer: where the next non-zero should land.
Scan with a read pointer from left to right.
When nums[read] != 0, swap with nums[write] and increment write.
Stable order is preserved because non-zeros are processed in original sequence.

💻 Solution Approaches

Approach 1: Build New Array (Not Preferred)

Time: O(N) | Space: O(N)

Collect non-zeros, then append zeros. Easy to reason about, but violates the in-place spirit and uses extra memory.

Approach 2: In-Place Two Pointers (Recommended)

Time: O(N) | Space: O(1)

Python Implementation

          from typing import List


def move_zeroes(nums: List[int]) -> None:
    """
    Rearrange nums in-place so that all zeros are moved to the end,
    preserving non-zero relative order.

    Time: O(N)
    Space: O(1)
    """
    write = 0

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

JavaScript Implementation

          function moveZeroes(nums) {
  let write = 0;

  for (let read = 0; read < nums.length; read += 1) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write += 1;
    }
  }
}
        

🔍 Step-by-Step Walkthrough

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

Start: write=0
read=0 -> 0, skip
read=1 -> 1, swap(0,1): [1,0,0,3,12], write=1
read=2 -> 0, skip
read=3 -> 3, swap(1,3): [1,3,0,0,12], write=2
read=4 -> 12, swap(2,4): [1,3,12,0,0]

⚡ Complexity Analysis

Time: O(N) because each index is visited once by read, and each swap is constant time.

Space: O(1) because we only store two pointers regardless of input size.

🔧 Edge Cases

Already compacted: [1,2,3] -> unchanged.
All zeros: [0,0,0] -> unchanged.
Single element: [0] or [5].
Zeros interleaved with negatives: [0,-1,0,-2].

🧪 Test Cases

Python

def test_move_zeroes():
    data = [0, 1, 0, 3, 12]
    move_zeroes(data)
    assert data == [1, 3, 12, 0, 0]

    data = [0, 0, 1]
    move_zeroes(data)
    assert data == [1, 0, 0]

    data = [4, 0, 5, 0, 0, 3]
    move_zeroes(data)
    assert data == [4, 5, 3, 0, 0, 0]

    print("all tests passed")

JavaScript

function testMoveZeroes() {
  const a = [0, 1, 0, 3, 12];
  moveZeroes(a);
  console.assert(JSON.stringify(a) === JSON.stringify([1, 3, 12, 0, 0]), "test 1");

  const b = [0, 0, 1];
  moveZeroes(b);
  console.assert(JSON.stringify(b) === JSON.stringify([1, 0, 0]), "test 2");

  const c = [4, 0, 5, 0, 0, 3];
  moveZeroes(c);
  console.assert(JSON.stringify(c) === JSON.stringify([4, 5, 3, 0, 0, 0]), "test 3");

  console.log("all tests passed");
}

💼 Interview Tips

Clarify that the operation must be in-place.
State pointer invariants before writing code.
Mention why order is preserved in this strategy.
Show test coverage for mixed and all-zero inputs.

🎓 Key Takeaways

Two pointers solve this in one pass and constant space.
Swapping non-zeros forward keeps relative order intact.
In-place array transformations depend on invariant design.

← Back to All Algorithms