23. Move Zeroes
🔗 LeetCode Problem: 283. Move Zeroes
📊 Difficulty: Easy
🏷️ Topics: Array, Two Pointers
Problem Statement
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: You must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
Constraints:
- 1 <= nums.length <= 10^4
- -2^31 <= nums[i] <= 2^31 - 1
Follow up: Could you minimize the total number of operations done?
🎨 Visual Understanding
The Problem Visualized
Input: nums = [0, 1, 0, 3, 12]
Goal: Move all zeros to the end
Before: [0, 1, 0, 3, 12]
After: [1, 3, 12, 0, 0]
└─non-zero─┘└zeros┘
Relative order preserved:
Original non-zeros: 1, 3, 12
Final non-zeros: 1, 3, 12 ✓
Key Requirements
1. Move zeros to end
2. Maintain relative order of non-zeros
3. In-place (O(1) extra space)
4. Minimize operations
Example showing order preservation:
Input: [0, 1, 0, 3, 12]
Wrong: [12, 3, 1, 0, 0] ✗ (reversed order)
Right: [1, 3, 12, 0, 0] ✓ (order preserved)
Two Pointer Strategy
Use two pointers:
- left: position to place next non-zero
- right: scans through array
[0, 1, 0, 3, 12]
↑ ↑
left right
Found non-zero (1):
Place at left position
Move left forward
[1, 1, 0, 3, 12]
↑ ↑
left right
Continue until all non-zeros moved
Then fill remaining with zeros
🎯 Approach 1: Extra Array (Not Allowed)
The Most Natural Thinking 💭
Core Logic:
Use extra array to store result:
1. Iterate through original array
2. Add non-zeros to new array
3. Fill remaining positions with zeros
4. Copy back to original
Why This Works: - Simple and straightforward - Easy to understand - Guarantees correct order
Why This is NOT Valid: - Problem requires in-place modification - O(n) extra space violates constraint - Not the solution we need
Implementation (For Understanding Only)
// NOT VALID - Uses extra space
public void moveZeroes(int[] nums) {
int[] result = new int[nums.length];
int index = 0;
// Copy non-zeros
for (int num : nums) {
if (num != 0) {
result[index++] = num;
}
}
// Remaining positions already 0 (default)
// Copy back
for (int i = 0; i < nums.length; i++) {
nums[i] = result[i];
}
}
⏰ Time: O(n)
💾 Space: O(n) - violates constraint
🎯 Approach 2: Two Pass with Count
Thought Process 💭
Core Logic:
Two-pass approach:
Pass 1: Move all non-zeros to front
Pass 2: Fill remaining with zeros
1. Track position to place non-zeros
2. First pass: copy all non-zeros forward
3. Second pass: fill rest with zeros
Why This Works: - In-place modification - Maintains relative order - Clear and understandable
Why Not Optimal: - Two passes through array - Can be optimized to single pass
Implementation
public void moveZeroes(int[] nums) {
int pos = 0; // Position to place next non-zero
// Pass 1: Move all non-zeros to front
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[pos] = nums[i];
pos++;
}
}
// Pass 2: Fill remaining with zeros
for (int i = pos; i < nums.length; i++) {
nums[i] = 0;
}
}
Step-by-Step Execution: nums = [0,1,0,3,12]
Initial State:
═══════════════════════════════════════════════════════════════════
nums = [0, 1, 0, 3, 12]
pos = 0
Pass 1: Move non-zeros to front
═══════════════════════════════════════════════════════════════════
i=0: nums[0]=0 → zero, skip
pos stays 0
i=1: nums[1]=1 → non-zero!
nums[0] = 1
pos++ → pos=1
nums = [1, 1, 0, 3, 12]
i=2: nums[2]=0 → zero, skip
pos stays 1
i=3: nums[3]=3 → non-zero!
nums[1] = 3
pos++ → pos=2
nums = [1, 3, 0, 3, 12]
i=4: nums[4]=12 → non-zero!
nums[2] = 12
pos++ → pos=3
nums = [1, 3, 12, 3, 12]
Pass 2: Fill remaining with zeros
═══════════════════════════════════════════════════════════════════
pos=3, so fill from index 3 to end
i=3: nums[3] = 0
nums = [1, 3, 12, 0, 12]
i=4: nums[4] = 0
nums = [1, 3, 12, 0, 0]
═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [1, 3, 12, 0, 0]
═══════════════════════════════════════════════════════════════════
⏰ Time: O(n) - two passes
💾 Space: O(1) - in-place
✅ Approach 3: Swap Method (Optimal)
The Breakthrough Insight 💡
Core Logic:
Single pass with swap:
Use two pointers:
- left: position for next non-zero
- right: scans through array
When non-zero found:
Swap with position at left
Advance left
This maintains order AND minimizes operations!
Why This is Better: - Single pass through array - Minimizes swaps (only when needed) - O(1) space, O(n) time - Optimal solution!
Visual Process:
[0, 1, 0, 3, 12]
↑ ↑
left right
right=1 (non-zero): swap with left
[1, 0, 0, 3, 12]
↑ ↑
left right
right=3 (non-zero): swap with left
[1, 3, 0, 0, 12]
↑ ↑
left right
right=4 (non-zero): swap with left
[1, 3, 12, 0, 0]
↑ ↑
left right
Done!
Implementation
public void moveZeroes(int[] nums) {
int left = 0; // Position for next non-zero
// Single pass: when non-zero found, swap to front
for (int right = 0; right < nums.length; right++) {
if (nums[right] != 0) {
// Swap only if positions are different
if (left != right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
left++;
}
}
}
Step-by-Step Execution: nums = [0,1,0,3,12]
Initial State:
═══════════════════════════════════════════════════════════════════
nums = [0, 1, 0, 3, 12]
left = 0
right=0: nums[0]=0
═══════════════════════════════════════════════════════════════════
Zero → skip
left stays 0
nums = [0, 1, 0, 3, 12]
↑ ↑
left right
right=1: nums[1]=1
═══════════════════════════════════════════════════════════════════
Non-zero! Swap with left
Swap nums[0] and nums[1]
nums = [1, 0, 0, 3, 12]
left++ → left=1
↑ ↑
left right
right=2: nums[2]=0
═══════════════════════════════════════════════════════════════════
Zero → skip
left stays 1
nums = [1, 0, 0, 3, 12]
↑ ↑
left right
right=3: nums[3]=3
═══════════════════════════════════════════════════════════════════
Non-zero! Swap with left
Swap nums[1] and nums[3]
nums = [1, 3, 0, 0, 12]
left++ → left=2
↑ ↑
left right
right=4: nums[4]=12
═══════════════════════════════════════════════════════════════════
Non-zero! Swap with left
Swap nums[2] and nums[4]
nums = [1, 3, 12, 0, 0]
left++ → left=3
↑ ↑
left right
═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: [1, 3, 12, 0, 0]
═══════════════════════════════════════════════════════════════════
Another Example: nums = [0,0,1]
Initial: nums = [0, 0, 1], left=0
right=0: nums[0]=0 → skip
right=1: nums[1]=0 → skip
right=2: nums[2]=1 → non-zero!
Swap nums[0] and nums[2]
nums = [1, 0, 0]
left++ → left=1
Result: [1, 0, 0]
Example: No Zeros: nums = [1,2,3]
Initial: nums = [1, 2, 3], left=0
right=0: nums[0]=1 → non-zero
left==right (both 0) → no swap needed
left++ → left=1
right=1: nums[1]=2 → non-zero
left==right (both 1) → no swap needed
left++ → left=2
right=2: nums[2]=3 → non-zero
left==right (both 2) → no swap needed
left++ → left=3
Result: [1, 2, 3] (unchanged)
⏰ Time: O(n) - single pass
💾 Space: O(1) - only two pointers
🎯 Approach 4: Snowball Method (Creative Alternative)
Alternative Optimal Solution 💡
Core Logic:
Think of zeros as a "snowball" rolling through array:
Track snowball size (count of zeros seen)
When non-zero found:
Swap it back by snowball size
Visual: Zeros accumulate like a rolling snowball
Implementation
public void moveZeroes(int[] nums) {
int snowballSize = 0; // Count of zeros seen
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
snowballSize++;
} else if (snowballSize > 0) {
// Swap current element back by snowball size
int temp = nums[i];
nums[i] = 0;
nums[i - snowballSize] = temp;
}
}
}
Visual Example: nums = [0,1,0,3,12]
i=0: nums[0]=0 → snowballSize=1
[0, 1, 0, 3, 12]
i=1: nums[1]=1 (non-zero), snowballSize=1
Swap: nums[1]=0, nums[0]=1
[1, 0, 0, 3, 12]
i=2: nums[2]=0 → snowballSize=2
[1, 0, 0, 3, 12]
i=3: nums[3]=3 (non-zero), snowballSize=2
Swap: nums[3]=0, nums[1]=3
[1, 3, 0, 0, 12]
i=4: nums[4]=12 (non-zero), snowballSize=2
Swap: nums[4]=0, nums[2]=12
[1, 3, 12, 0, 0]
Result: [1, 3, 12, 0, 0]
⏰ Time: O(n)
💾 Space: O(1)
🔍 Edge Cases
Case 1: Single element zero
Input: nums = [0]
Output: [0]
Case 2: Single element non-zero
Input: nums = [1]
Output: [1]
Case 3: All zeros
Input: nums = [0,0,0]
Output: [0,0,0]
Case 4: No zeros
Input: nums = [1,2,3]
Output: [1,2,3]
Case 5: All zeros at beginning
Input: nums = [0,0,1,2,3]
Output: [1,2,3,0,0]
Case 6: All zeros at end
Input: nums = [1,2,3,0,0]
Output: [1,2,3,0,0]
Case 7: Alternating zeros
Input: nums = [0,1,0,2,0,3]
Output: [1,2,3,0,0,0]
Case 8: Two elements
Input: nums = [0,1]
Output: [1,0]
Common Mistakes
Mistake 1: Not checking if left != right before swap
❌ Wrong: Always swap even if same position
✓ Right: if (left != right) swap(...)
Reason: Unnecessary operation when positions same
Mistake 2: Incrementing left unconditionally
❌ Wrong:
if (nums[right] != 0) swap(...);
left++;
✓ Right:
if (nums[right] != 0) {
swap(...);
left++;
}
Mistake 3: Using two separate loops without need
❌ Wrong: One loop to find non-zeros, another to place
✓ Right: Single loop with swap is more efficient
Mistake 4: Not maintaining relative order
❌ Wrong: Moving non-zeros without preserving order
✓ Right: Process left-to-right, maintain sequence
Mistake 5: Creating new array
❌ Wrong: int[] result = new int[n]
✓ Right: Modify in-place
Mistake 6: Overcomplicating with sorting
❌ Wrong: Use sorting algorithms
✓ Right: Simple two-pointer approach
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Extra Array
Time: O(n)
Space: O(n)
Use: Violates in-place requirement
Approach 2: Two Pass
Time: O(n)
Space: O(1)
Use: Good, but two passes
Approach 3: Swap Method (OPTIMAL)
Time: O(n)
Space: O(1)
Use: Best - single pass, minimal operations
Approach 4: Snowball Method
Time: O(n)
Space: O(1)
Use: Creative alternative
🔑 The Core Insight
Problem: Move zeros to end, preserve order, in-place
Key observation: Use two pointers
→ left: position to place next non-zero
→ right: scans through array
When non-zero found at right:
→ Swap with position at left
→ Advance left pointer
Why swap works:
→ Maintains relative order of non-zeros
→ Automatically moves zeros to end
→ Single pass, minimal operations
🎯 Pattern Recognition
Problem Type: In-Place Array Reorganization
Core Pattern: Two Pointers (Fast & Slow)
When to Apply:
✓ Need to reorganize array elements
✓ Maintain relative order
✓ In-place modification required
✓ Partition based on condition
Key Techniques:
→ Slow pointer (left) tracks write position
→ Fast pointer (right) scans array
→ Swap elements to maintain order
→ Single pass optimization
Related Problems:
- Remove Element (LC 27)
- Remove Duplicates from Sorted Array (LC 26)
- Sort Colors (LC 75)
- Partition Array (LC 2161)
🧠 Interview Strategy
Step 1: "Need to move zeros to end, maintain order"
Step 2: "Could use extra array - O(n) space"
Step 3: "Better: two pointers in-place"
Step 4: "Left tracks position for non-zeros"
Step 5: "Swap when non-zero found - O(n) time, O(1) space"
📝 Quick Revision Notes
🎯 Core Concept:
Use two pointers: left (write position for non-zeros) and right (scan array). When non-zero found, swap with left position and advance left.
⚡ Quick Implementation:
public void moveZeroes(int[] a) {
int len = a.length;
int i = 0;
int j = 0;
// move i to 1st zero - pre-arrange i
while (i < len && a[i] != 0) {
i++;
}
// move j to 1st non-zero - - pre-arrange j
while (j < len && a[j] == 0) {
j++;
}
// process now
while(i < len && j < len) {
// found non-zero at index j. Move number from index j to index i
// and make number at index j to 0
if(a[j] != 0 && i < j) {
a[i] = a[j];
a[j] = 0;
// move i to next zero (same logic as above)
while (i < len && a[i] != 0) {
i++;
}
// move j to next non-zero (same logic as above)
while (j < len && a[j] == 0) {
j++;
}
} else {
j++; // did not find non-zero. Simply move
}
}
}
🔑 Key Insights:
- Two pointers: left (slow/write), right (fast/read)
- Swap when non-zero: preserves order
- Check left != right: avoid unnecessary swaps
- Advance left: only when non-zero found
- Single pass: O(n) time complexity
- In-place: O(1) extra space
- Order preserved: non-zeros stay in sequence
- Zeros moved: automatically pushed to end by swaps
🎪 Memory Aid:
"Left writes non-zeros, right finds them, swap and advance!"
Think: "Swap non-zeros forward, zeros naturally fall back"
Related Patterns
- Remove Element (LC 27)
- Remove Duplicates from Sorted Array (LC 26)
- Sort Colors (LC 75)
- Partition Array (LC 2161)
Happy practicing! 🎯