Mohammed mhanna

Posted on Sep 21

🎯 Master the Move Zeros Algorithm:

#algorithms #learning #java #programming

🧩 The Problem
Given an array like [0, 1, 0, 3, 12], move all zeros to the end: [1, 3, 12, 0, 0]
Constraints:

Maintain relative order of non-zero elements
Do it in-place (O(1) space)
Single pass preferred (O(n) time)

💡 The Solution: Two Pointers Magic

public class MoveZeros {
    public static void moveZeroes(int[] nums) {
        int left = 0; // position to place next non-zero

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                // Swap non-zero element to the left pointer position
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++; // move to next position for non-zero
            }
        }
    }
}

🔍 Step-by-Step Trace
Initial Array: [0, 1, 0, 3, 12]

Step 1: right=0, nums[0]=0
❌ Skip (zero)
Array: [0, 1, 0, 3, 12], left=0

Step 2: right=1, nums[1]=1

✅ Swap positions 0↔1, left++
Array: [1, 0, 0, 3, 12], left=1

Step 3: right=2, nums[2]=0
❌ Skip (zero)
Array: [1, 0, 0, 3, 12], left=1

Step 4: right=3, nums[3]=3
✅ Swap positions 1↔3, left++

Array: [1, 3, 0, 0, 12], left=2

Step 5: right=4, nums[4]=12
✅ Swap positions 2↔4, left++
Array: [1, 3, 12, 0, 0], left=3

Final Result: [1, 3, 12, 0, 0] ✨

🧠 The Key Insight: The Invariant

"Everything before left contains only non-zero elements in their original relative order"

This invariant is maintained automatically by the algorithm:

🎯 left only moves when we place a non-zero element
➡️ We process elements left-to-right (preserves order)
📍 Each non-zero goes to the next available position
🚧 left acts as a boundary: "completed section" vs "work in progress"

⚠️ Common Mistake: Where NOT to put left++

// ❌ WRONG - This breaks everything!
for (int right = 0; right < nums.length; right++) {
    if (nums[right] != 0) {
        swap(nums[left], nums[right]);
    }
    left++; // ⚠️ WRONG POSITION - increments even for zeros!
}

Why this fails:

left advances even for zeros
We lose track of where to place non-zeros
Result: 0, 1, 0, 3, 12 💥

The fix: left++ must be inside the if-block!

🔧 Two Cases of Swapping

Case A: left == right

// Swapping element with itself - no visual change
nums[2] ↔ nums[2]  // No effect

Case B: left < right

// Swapping non-zero with a zero to its left
nums[1] ↔ nums[3]  // 0 ↔ 3 = moves 3 forward, 0 backward

📊 Algorithm Analysis

Time Complexity: O(n)
→ Single pass through array with constant work per element

Space Complexity: O(1)
→ Only two pointer variables (left, right)

Stability: ✅ Yes
→ Maintains relative order of non-zero elements

In-place: ✅ Yes

→ Modifies original array without extra space

🎨 Pattern Recognition: Two-Pointer Partitioning
This algorithm follows the partition pattern:

🎯 One pointer (left) maintains the "good" section
🔍 Other pointer (right) explores to find elements for the "good" section
🔄 We build the result incrementally

DEV Community

🎯 Master the Move Zeros Algorithm:

Top comments (0)