🧩 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
Similar problems:
Move negative numbers to left
Separate even/odd numbers
Dutch National Flag (3-way partitioning)
💭 Mental Model
Think of left as a cursor with a simple rule:
"Everything before me is exactly what we want in the final result"
When we find a non-zero → place it at cursor → move cursor forward
When we find a zero → ignore it → cursor stays put (waiting for next non-zero)
🚀 Practice Variations
Once you master this, try these related problems:
Remove Element: Remove all instances of a value
Remove Duplicates: Keep only unique elements
Sort Colors: Sort array of 0s, 1s, and 2s
Partition Array: Separate elements based on condition
🎯 Key Takeaways
Two pointers can solve complex rearrangement problems efficiently
Invariants help us understand why algorithms work
Placement of increment operations is crucial
Pattern recognition helps solve similar problems faster
What's your favorite two-pointer algorithm? Drop a comment and let's discuss! 💬