Move Zeroes (LeetCode 283) — Two Pointers, and the Write Count

Problem Statement#

Given an integer array nums, move all zeroes to the end of it while maintaining the relative order of the non-zero elements. You must do this in place without making a copy of the array.

Input:  nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
 
Input:  nums = [0]
Output: [0]
 
Input:  nums = [1, 2, 3]
Output: [1, 2, 3]     (already done; nothing moves)

Constraints: 1 <= nums.length <= 10^4 and -2^31 <= nums[i] <= 2^31 - 1.

LeetCode 283 adds a follow-up that most write-ups repeat and then ignore: "Could you minimize the total number of operations done?" Hold on to it. It is the second half of this page, and it is the only part of this problem that is actually interesting.

The Short Answer#

Keep a write pointer at the front of the array. Scan with a read pointer; each time you meet a non-zero value, write it at the write pointer and advance it. When the scan ends, everything from the write pointer to the end is leftover, so fill it with zeroes. One pass, O(n) time, O(1) extra space.

The Invariant Does All the Work#

Two-pointer code is short enough that people memorise it instead of understanding it, and then cannot reproduce it under pressure three weeks later. The thing worth memorising is not the loop. It is this sentence:

Everything before write is the non-zero values seen so far, in their original order.

Check it at each stage and the code writes itself. Before the loop, write is 0 and "everything before index 0" is the empty prefix, which vacuously holds. Each step preserves it: a zero is skipped, so the prefix is untouched; a non-zero is appended to the prefix and write moves up one. When read falls off the end, the prefix contains every non-zero in order — which is the answer, minus the trailing zeroes.

One consequence matters for correctness. Because write only advances when read does, and both start at 0, write <= read holds forever. The cell you are writing into has already been read on this iteration or an earlier one, so its old value is safely captured. That is why this is genuinely in place and why no temporary array is needed.

Run It Yourself#

Reading a dry run is not the same as tracing one. Interviewers ask you to walk through your own array a step at a time precisely because that is where memorised solutions fall apart. Change the input below and step through it — try an array with no zeroes at all, then one that is all zeroes, and watch what write does in each.

Two things are worth pausing on while you step. First, on [1, 2, 3] the copy at line 4 writes each value onto itself, because write and read are the same index — correct, but pure waste. Second, on [0, 0, 0] the scan never writes anything and the fill does all the work. Those two inputs are the extremes that the follow-up question is about.

Solutions#

Python#

from typing import List
 
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        write = 0
        for value in nums:
            if value != 0:
                nums[write] = value
                write += 1
        for i in range(write, len(nums)):
            nums[i] = 0

JavaScript#

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

Java#

class Solution {
    public void moveZeroes(int[] nums) {
        int write = 0;
        for (int value : nums) {
            if (value != 0) nums[write++] = value;
        }
        while (write < nums.length) nums[write++] = 0;
    }
}

Minimising Operations, Properly#

Now the follow-up. Two solutions to this problem are taught interchangeably, and they are not the same program.

The version above always performs exactly n writes: one per non-zero during the scan, one per trailing slot during the fill. The input makes no difference at all — the tracer prints the count at the end, and it is the array length every time.

The swap version behaves differently:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        write = 0
        for read in range(len(nums)):
            if nums[read] != 0:
                nums[write], nums[read] = nums[read], nums[write]
                write += 1

It does one swap per non-zero, and a swap is two writes — but it does nothing at all for every zero it passes. So the two versions trade places depending on how zero-heavy the input is:

Read across the first row. On an array with no zeroes — the case where the correct answer is to do nothing — the plain swap version does twice as much work as the overwrite version, swapping every element with itself. That is the opposite of minimising operations.

One line fixes it:

if nums[read] != 0 and read != write:
    nums[write], nums[read] = nums[read], nums[write]

With the guard, the swap version never does worse than the overwrite version and often does much better. That is the honest answer to the follow-up, and it is a far more interesting thing to say out loud than "use two pointers".

Where It Goes Wrong#

Rebinding the name instead of mutating the list. This is the single most common reason a correct-looking Python solution scores zero. Writing nums = [x for x in nums if x != 0] + [0] * zeros changes only the local reference; the caller's list is untouched, the function returns None, and the grader sees the original array. The Python tutorial is explicit about the convention behind this: "You might have noticed that methods like insert, remove or sort that only modify the list have no return value printed – they return the default None. This is a design principle for all mutable data structures in Python." (Data Structures, python.org). Mutate through indices, or assign into the slice with nums[:] = ....

Leaving the swap unguarded. Covered above. Correct, wasteful, and it fails the exact follow-up the problem asks.

Counting zeroes, then shifting one slot at a time. Two passes are fine; shifting the tail once per zero is not. On [0, 0, 0, ..., 1] that degrades to O(n²).

Treating the ordering requirement as optional. [0, 1, 0, 3, 12] must give [1, 3, 12, 0, 0], not [12, 1, 3, 0, 0]. Any solution that swaps a non-zero with the array's tail breaks this — which is exactly why the next problem below is easier than this one.

The Problems Next Door#

Remove Element — when order is free#

LeetCode 27 removes every occurrence of a value and returns the new length, and it says explicitly that the order of the remaining elements may be changed. Dropping that one requirement unlocks a cheaper algorithm: swap each unwanted element with the last unprocessed one and shrink the array.

def remove_element(nums, val):
    n = len(nums)
    i = 0
    while i < n:
        if nums[i] == val:
            nums[i] = nums[n - 1]   # pull from the tail, do not advance i
            n -= 1
        else:
            i += 1
    return n

That is one write per removed element rather than one per surviving element. On an array that is almost entirely val, it is dramatically cheaper. The general lesson is worth carrying: when order is free, take from the end.

Remove Duplicates from Sorted Array#

LeetCode 26 is the same write-pointer skeleton with a different skip condition — advance write only when the value differs from the last one written. If you can write Move Zeroes from memory you already know it, and the post on removing duplicates from a sorted array walks the variant.

Sort Colors#

LeetCode 75 is the three-way version: instead of one write pointer you carry a low and a high boundary and partition into three regions in a single pass. It is Dijkstra's Dutch national flag partition, and it is what this idea grows into — see Sort Colors.

Key Takeaways#

• State the invariant before the code: everything before write is the non-zero values seen so far, in order. The loop follows from it.
• write never overtakes read, which is why writing into the array you are still scanning is safe and no copy is needed.
• Overwrite-then-fill costs exactly n writes on every input. Swap costs two per non-zero and nothing per zero.
• Guarding the swap with read != write removes the self-swap waste and is the real answer to the follow-up — zero writes on a zero-free array.
• In Python, rebinding nums rather than mutating it is the most common cause of a correct-looking solution failing.
• Drop the ordering requirement and this becomes Remove Element, where pulling from the tail is cheaper. Add a third bucket and it becomes Sort Colors.
• If you can trace it on [1, 2, 3] and [0, 0, 0] without running it, you know it. If you can only recite the loop, you do not.