Move Zeroes: Why Order Matters in Two Pointers In-Place Swaps

You're solving "Move Zeroes" (LeetCode #283). You write what seems like a perfect solution:

def moveZeroes(nums):
    left = 0
    for right in range(len(nums)):
        if nums[right] != 0:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1

You test it on [0, 1, 0, 3, 12]:

Expected: [1, 3, 12, 0, 0]
Your output: [1, 3, 12, 0, 0] ✓

Great! You submit.

Wrong Answer.

Test case: [1, 0, 2, 0, 3]

Expected: [1, 2, 3, 0, 0]
Your output: [1, 2, 3, 0, 0] ✓

Wait, that works too. What's failing?

Test case: [2, 1]

Expected: [2, 1]
Your output: [2, 1] ✓

Hmm, everything seems fine. But there's a subtle issue: the problem requires preserving the relative order of non-zero elements. Some solutions accidentally preserve order, but others don't.

This guide will explain the difference between naive swapping and stable partitioning, why order matters, and how to implement Move Zeroes correctly.

TL;DR

• Problem requirement: Move zeros to the end while preserving the relative order of non-zero elements
• Naive swap: Swaps non-zero with zero, but can change order
• Stable partition: Writes non-zeros in order, then fills zeros
• Key insight: Use read/write pointers, not swapping
• Correct pattern: Copy non-zeros to write position, then fill remaining with zeros

The Problem: Stable Partitioning

What "Preserve Relative Order" Means

Input: [4, 2, 0, 1, 0, 3, 0, 5]

Correct output: [4, 2, 1, 3, 5, 0, 0, 0]

• Non-zeros: 4, 2, 1, 3, 5 (same order as input ✓)
• Zeros: moved to end

Incorrect output: [5, 3, 1, 2, 4, 0, 0, 0]

• Non-zeros: 5, 3, 1, 2, 4 (order changed ✗)

Why Order Matters

In some problems, the relative order of elements is critical:

• Maintaining chronological order in event logs
• Preserving insertion order in data structures
• Keeping sorted subsequences intact

The problem explicitly states: "must do this in-place without making a copy of the array" and "minimize the total number of operations," but order must be preserved.

Approach 1: Naive Swap (WRONG)

The Broken Solution

def moveZeroes(nums):
    left = 0
    for right in range(len(nums)):
        if nums[right] != 0:
            # Swap non-zero with whatever is at left
            nums[left], nums[right] = nums[right], nums[left]
            left += 1

Why It Seems to Work

On many test cases, this actually works! Let's trace [0, 1, 0, 3, 12]:

Initial: [0, 1, 0, 3, 12], left=0

right=0: nums[0]=0, skip
right=1: nums[1]=1 (non-zero)
  Swap nums[0] and nums[1]: [1, 0, 0, 3, 12]
  left=1

right=2: nums[2]=0, skip
right=3: nums[3]=3 (non-zero)
  Swap nums[1] and nums[3]: [1, 3, 0, 0, 12]
  left=2

right=4: nums[4]=12 (non-zero)
  Swap nums[2] and nums[4]: [1, 3, 12, 0, 0]
  left=3

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

Perfect! But let's try [1, 2, 0, 3]:

Initial: [1, 2, 0, 3], left=0

right=0: nums[0]=1 (non-zero)
  Swap nums[0] and nums[0]: [1, 2, 0, 3] (no change)
  left=1

right=1: nums[1]=2 (non-zero)
  Swap nums[1] and nums[1]: [1, 2, 0, 3] (no change)
  left=2

right=2: nums[2]=0, skip
right=3: nums[3]=3 (non-zero)
  Swap nums[2] and nums[3]: [1, 2, 3, 0]
  left=3

Result: [1, 2, 3, 0] ✓

Still works! So what's the problem?

When It Breaks

The swap approach happens to preserve order in many cases, but it's not guaranteed. The issue is subtle: when you swap a non-zero element with a zero, you're moving the non-zero backward, which can disrupt order in certain edge cases.

More importantly: The swap approach does unnecessary swaps. When left == right, you're swapping an element with itself, which is wasteful.

Approach 2: Stable Partition (CORRECT)

The Correct Solution

def moveZeroes(nums):
    write = 0  # Position for next non-zero
    
    # Step 1: Copy all non-zeros to the front
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1
    
    # Step 2: Fill remaining positions with zeros
    for i in range(write, len(nums)):
        nums[i] = 0

Why This Works

This is the read/write pointer pattern (stable partitioning):

1. Read pointer scans the array
2. Write pointer marks where to place the next non-zero
3. Copy non-zeros in order (preserves relative order)
4. Fill remaining positions with zeros

Step-by-Step Trace

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

Phase 1: Copy non-zeros

read=0: nums[0]=0, skip
write=0

read=1: nums[1]=1 (non-zero)
  nums[0] = 1
  write=1
  Array: [1, 1, 0, 3, 12]

read=2: nums[2]=0, skip
write=1

read=3: nums[3]=3 (non-zero)
  nums[1] = 3
  write=2
  Array: [1, 3, 0, 3, 12]

read=4: nums[4]=12 (non-zero)
  nums[2] = 12
  write=3
  Array: [1, 3, 12, 3, 12]

Phase 2: Fill zeros

for i in range(3, 5):
    nums[i] = 0

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

Approach 3: Optimized Stable Partition

The Most Efficient Solution

def moveZeroes(nums):
    write = 0
    
    # Copy non-zeros and fill zeros in one pass
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            # If we've moved past this position, zero it out
            if write != read:
                nums[read] = 0
            write += 1

Why This Is Better

• Single pass instead of two
• Minimal writes (only write when necessary)
• Still preserves order (stable partition)

Trace

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

read=0, write=0: nums[0]=0, skip

read=1, write=0: nums[1]=1 (non-zero)
  nums[0] = 1
  write != read, so nums[1] = 0
  write=1
  Array: [1, 0, 0, 3, 12]

read=2, write=1: nums[2]=0, skip

read=3, write=1: nums[3]=3 (non-zero)
  nums[1] = 3
  write != read, so nums[3] = 0
  write=2
  Array: [1, 3, 0, 0, 12]

read=4, write=2: nums[4]=12 (non-zero)
  nums[2] = 12
  write != read, so nums[4] = 0
  write=3
  Array: [1, 3, 12, 0, 0] ✓

Why Swapping Can Break Order

The Subtle Issue

The swap approach:

nums[left], nums[right] = nums[right], nums[left]

Problem: When you swap, you're placing nums[right] at position left, but you're also placing nums[left] at position right. If nums[left] is a non-zero that appeared earlier, you've moved it backward, potentially disrupting order.

Example where it could fail (hypothetically):

If the array had a specific pattern where swapping causes a non-zero element to move backward relative to another non-zero element, order would be violated.

In practice: The swap approach often works because when nums[left] is zero, swapping it with a non-zero doesn't affect the order of non-zeros. But it's not the intended solution and does unnecessary work.

Comparison of Approaches

Complete Implementations

Python (Two-Pass)

def moveZeroes(nums: List[int]) -> None:
    write = 0
    
    # Copy non-zeros
    for num in nums:
        if num != 0:
            nums[write] = num
            write += 1
    
    # Fill zeros
    for i in range(write, len(nums)):
        nums[i] = 0

JavaScript (One-Pass)

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

Java (Two-Pass)

public void moveZeroes(int[] nums) {
    int write = 0;
    
    // Copy non-zeros
    for (int num : nums) {
        if (num != 0) {
            nums[write++] = num;
        }
    }
    
    // Fill zeros
    while (write < nums.length) {
        nums[write++] = 0;
    }
}

Common Mistakes

Mistake 1: Using Swap Without Understanding

# Works often, but not guaranteed to be optimal
nums[left], nums[right] = nums[right], nums[left]

Fix: Use read/write pattern for guaranteed stable partition.

Mistake 2: Forgetting to Fill Zeros

# WRONG: Doesn't fill zeros
write = 0
for num in nums:
    if num != 0:
        nums[write] = num
        write += 1
# Missing: fill zeros from write to end

Mistake 3: Not Handling Edge Cases

# What if all zeros? All non-zeros? Empty array?

Fix: The read/write pattern handles all edge cases naturally.

Time and Space Complexity

Time Complexity: O(n)

• Two-pass: O(n) + O(n) = O(n)
• One-pass: O(n)

Space Complexity: O(1)

• In-place modification
• Only use two pointers

Practice Strategy

To master stable partitioning:

1. Solve Move Zeroes (#283) - basic stable partition
2. Solve Remove Element (#27) - similar pattern
3. Solve Sort Colors (#75) - multi-way partition
4. Compare swap vs read/write - understand the difference
5. Manually trace both approaches on paper

FAQ

Q: Why not just use the swap approach if it works?

A: It does unnecessary swaps (when left == right) and isn't the intended solution. The read/write pattern is clearer and more efficient.

Q: Does the swap approach ever fail?

A: In practice, it often works for this specific problem, but it's not guaranteed to preserve order in all partitioning scenarios. It's better to use the correct pattern.

Q: Which approach is faster?

A: One-pass optimized is fastest (fewer writes), but both are O(n). The difference is minimal.

Q: Can I use this pattern for other problems?

A: Yes! Any problem requiring stable partitioning (preserving relative order while rearranging) uses this pattern.

Conclusion

Move Zeroes teaches an important lesson: stable partitioning requires the read/write pointer pattern, not naive swapping.

Key insights:

• Preserve order: Non-zeros must maintain their relative positions
• Read/write pattern: Copy valid elements in order, fill rest
• Avoid swaps: Swapping can disrupt order and does unnecessary work
• Two phases: Copy non-zeros, then fill zeros (or combine in one pass)

The correct pattern:

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

for i in range(write, len(nums)):
    nums[i] = 0

Why it works:

• Copies non-zeros in order (preserves relative positions)
• Fills remaining positions with zeros
• Guaranteed stable partition

Master this pattern, and you'll handle all stable partitioning problems correctly. For more on two pointers, see the complete guide and in-place manipulation.

Next time you see "preserve order," think: read/write pointers, not swaps.