Move Zeroes — InterviewPrepKit

Solving tips

Only nonzeros have destinations: use a slow write pointer and a fast scan pointer, this is a stable in-place partition on 'is nonzero'.
One-pass swap: when fast finds a nonzero, swap it into nums[slow] and advance slow; the region between the pointers is always zeros.
Move nonzeros forward, never move/delete zeros (list.remove in a loop is O(n^2) and skips elements); preserve relative order by writing left-to-right.
O(n) time, O(1) space; guard with `if slow != fast` to skip self-swaps and minimize writes for the follow-up.

Problem

Given an integer array nums, push every 0 to the back of the array while keeping all the nonzero elements in their original relative order. Do it in place — mutate nums rather than returning a new array.

Follow-up: minimize the total number of operations (writes/swaps).

Examples

nums = [0,1,0,3,12] → [1,3,12,0,0] The nonzeros 1,3,12 keep their order; the two zeros slide to the end.
nums = [0] → [0] A single zero stays put — there is nothing to reorder.
nums = [2,1] → [2,1] No zeros at all; the array is untouched.

Constraints

1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1
Must be in place (O(1) extra space expected); a single O(n) pass is achievable.

Think about it first

Hint 1

"Zeros at the end, nonzeros in order" means the final array is just the nonzero subsequence followed by padding. Could you compute where each nonzero *belongs*?

Hint 2

Keep a slow pointer marking the next slot to fill with a nonzero value, and a fast pointer scanning the array. What invariant does the slow pointer maintain?

Hint 3

Invariant: everything left of the slow pointer is the nonzeros seen so far, in order. When the fast pointer hits a nonzero, swap it into the slow slot and advance slow. After the scan, all zeros have been swapped behind the slow pointer automatically.

TL;DR

Slow/fast two pointers with swaps (one pass, in place) — O(n) time, O(1) space.

Approach 1 — Brute force: rebuild in a new list

Collect the nonzeros, count the zeros, and write the reconstructed array back.

class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        nonzeros = [x for x in nums if x != 0]
        zeros = len(nums) - len(nonzeros)
        nums[:] = nonzeros + [0] * zeros

Time: O(n).
Space: O(n) for the temporary list.

Time-wise nothing kills it — it’s the in-place requirement that rules it out: the problem explicitly forbids making a copy of the array, and O(n) scratch space is exactly that.

Approach 2 — Overwrite then back-fill zeros

The insight: you never need to move zeros — only nonzeros have destinations. Copy each nonzero forward to the next write slot, then overwrite everything after the last write slot with zeros.

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

Walkthrough on nums = [0,1,0,3,12]:

read x	action	nums after	write
0	skip	`[0,1,0,3,12]`	0
1	`nums[0] = 1`	`[1,1,0,3,12]`	1
0	skip	`[1,1,0,3,12]`	1
3	`nums[1] = 3`	`[1,3,0,3,12]`	2
12	`nums[2] = 12`	`[1,3,12,3,12]`	3

Back-fill indices 3..4 with zeros → [1,3,12,0,0].

Time: O(n) — two passes.
Space: O(1).

Writes: one per nonzero plus one per trailing slot — up to n total even when the array needs no change.

Approach 3 — One-pass swap (slow/fast pointers)

The insight: maintain the invariant nums[0:slow] holds exactly the nonzeros seen so far, in order; nums[slow:fast] is all zeros. When fast finds a nonzero, swapping it with nums[slow] extends the nonzero prefix by one and relocates a zero in the same move — no back-fill pass, and no writes at all while the prefix is already correct.

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

Walkthrough on nums = [0,1,0,3,12]:

fast	nums[fast]	action	nums after	slow
0	0	skip	`[0,1,0,3,12]`	0
1	1	swap idx 0 ↔ 1	`[1,0,0,3,12]`	1
2	0	skip	`[1,0,0,3,12]`	1
3	3	swap idx 1 ↔ 3	`[1,3,0,0,12]`	2
4	12	swap idx 2 ↔ 4	`[1,3,12,0,0]`	3

Result: [1,3,12,0,0]. Note the middle region nums[slow:fast] was zeros at every step, which is why each swap parks a zero correctly. When the array has no zeros, slow == fast throughout and every swap is a harmless self-swap — zero net data movement, satisfying the “minimize operations” follow-up (add an if slow != fast guard to skip even those writes).

Time: O(n) — single pass.
Space: O(1).

This is the partition step of quicksort (Lomuto scheme) specialized to the predicate “is nonzero” — a stable-for-the-kept-side, in-place partition.

Common pitfalls

Moving zeros instead of nonzeros (e.g., deleting zeros and appending) — list.remove inside a loop is O(n^2) and skips elements while iterating.
Breaking relative order by swapping nonzeros with the last zero from the back — order of the nonzeros must be preserved, so the write frontier must move left-to-right.
Forgetting the back-fill pass in Approach 2, leaving stale values (like the trailing 3,12 mid-walkthrough) behind the write pointer.
Returning a new list — the judge checks the mutated nums, and the signature returns None.

Pattern takeaway

The slow/fast pointer pair is an in-place stable partition: slow marks the boundary of “output built so far,” fast scans for the next element that belongs in it. State the invariant of the region between the pointers before coding — if that region is provably “all rejects,” a single swap per accepted element is both correct and write-minimal. The same skeleton solves Remove Duplicates, Remove Element, and quicksort’s partition.