Move Zeroes LeetCode 283 Deep Dive

LeetCode 283 — Move Zeroes — gives you an integer array nums and asks you to move all 0s to the end of the array while maintaining the relative order of the non-zero elements. The operation must be performed in-place without making a copy of the array. This is a classic partitioning problem that appears frequently at the start of coding interviews.

The naive approach — creating a new array of non-zero elements and appending zeros — is disqualified by the in-place constraint. The slightly smarter approach of bubble-sorting zeros to the right works but is O(n^2). The optimal two-pointer partition achieves the goal in O(n) time with O(1) space: one pass, one loop, no extra memory.

Move Zeroes is deceptively simple to state but tests whether you can apply the two-pointer partition pattern cleanly. It is closely related to Partition Array (Dutch Flag), Remove Element, and Remove Duplicates — all members of the same two-pointer family that shows up repeatedly in technical interviews.

The two-pointer partition uses a slow pointer and a fast pointer. The slow pointer (often called the write head) tracks the next available position where a non-zero element should be placed. The fast pointer (the read head) scans every element in the array from left to right. When the fast pointer encounters a non-zero element, it swaps that element with the element at the slow pointer's position, then both pointers advance. When the fast pointer finds a zero, only the fast pointer advances.

After the fast pointer has scanned the entire array, every non-zero element has been swapped into the prefix [0..slow-1] in its original relative order. All positions from slow onward contain zeros — not because we explicitly wrote zeros there, but because the swap operation moved the zeros left as non-zero elements were swapped right. The zeros naturally accumulate in the tail.

The two-pointer partition is O(n) time because the fast pointer visits each element exactly once and the slow pointer never exceeds the fast pointer. It is O(1) space because only the two pointer variables are used beyond the input array. No extra arrays, no hash maps, no sorting.

The algorithm initializes the slow pointer at index 0. The fast pointer then iterates through every index from 0 to n-1. At each step, if nums[fast] is not zero, we swap nums[slow] and nums[fast] and increment slow. If nums[fast] is zero, we skip — only fast advances. After the loop completes, all non-zero elements occupy positions 0 through slow-1, and all positions slow through n-1 contain zeros.

The swap is the key operation. When fast points to a non-zero element and slow < fast, nums[slow] must be zero (every element between slow and fast is a zero encountered earlier). Swapping moves the non-zero element to the write head and sends the zero backward toward the growing tail. When slow == fast, swapping is a no-op (swapping an element with itself), so no special case is needed.

The algorithm runs in a single pass. There are no nested loops, no recursion, and no data structures beyond the two pointer variables. The total number of swaps equals the number of non-zero elements that were to the right of at least one zero — which is at most n swaps in the worst case.

A memorable way to understand the algorithm is the snowball analogy. Imagine the fast pointer rolling a snowball as it moves right across the array. Each zero it passes gets absorbed into the snowball, making the snowball one element larger. Each non-zero element it passes hops over the snowball — the swap sends the non-zero element to the front of the snowball and a zero to the back. The snowball always stays together as a contiguous block of zeros in the middle of the array.

At the start, the snowball is empty (slow == fast == 0). After encountering the first zero, the snowball has size 1. After encountering k zeros, the snowball has size k. The slow pointer always points to the left edge of the snowball — where the next non-zero element will land after hopping over it. The snowball's right edge is the fast pointer.

By the end of the scan, the snowball has rolled all the way to the right and come to rest at the tail of the array. Every non-zero element has already hopped over the snowball to the left. The result: non-zero elements fill the front in original order, the snowball of zeros fills the back.

The swap version performs at most n swaps. But when the array has many zeros, we can reduce the total number of write operations by using the overwrite approach instead. First, iterate through the array and copy every non-zero element to the front: for each element, if nums[fast] != 0, set nums[slow] = nums[fast] and increment slow. After this pass, the first slow positions hold all non-zero elements in order.

The second step fills the tail with zeros: for each index from slow to n-1, set nums[i] = 0. The total writes are (number of non-zero elements) + (number of zeros). For a dense array (few zeros) this is roughly 2n writes, comparable to the swap version. For a sparse array (many zeros) this is much better: only the non-zero elements are recopied, then zeros are written once to the tail. The swap version, by contrast, does a swap for every non-zero element that must move.

The trade-off: the swap version is preferred in general because it handles partitioning on any value (not just 0) and works correctly even when the partition value appears in the "keep" portion. The overwrite version is faster when zeros are abundant and you want to minimize writes — but it requires knowing that the fill value (zero) is a constant, not a value copied from the array.

Python swap version: def moveZeroes(nums): slow = 0; for fast in range(len(nums)): if nums[fast] != 0: nums[slow], nums[fast] = nums[fast], nums[slow]; slow += 1. Four lines, no imports, in-place. Time O(n), space O(1). Python overwrite version: slow = 0; for num in nums: if num != 0: nums[slow] = num; slow += 1; for i in range(slow, len(nums)): nums[i] = 0. Five lines, two passes, still O(n) time O(1) space.

Java swap version: public void moveZeroes(int[] nums) { int slow = 0; for (int fast = 0; fast < nums.length; fast++) { if (nums[fast] != 0) { int tmp = nums[slow]; nums[slow] = nums[fast]; nums[fast] = tmp; slow++; } } } Five lines in the method body, one loop, no extra space. Java overwrite version: first loop writes non-zeros; second loop nums[i] = 0 from slow to nums.length - 1. Both are O(n) time O(1) space.

The swap version is preferred in interviews because it demonstrates mastery of the two-pointer partition pattern, which generalizes to Sort Colors (Dutch Flag), Remove Element, Partition Array, and Quick Sort's partition step. Recognizing this family and applying the same template is a strong signal in technical interviews.

Move Zeroes belongs to the two-pointer partition family. Sort Colors (LeetCode 75, Dutch National Flag) is the most direct generalization: instead of partitioning on a single value (0 vs non-zero), it partitions on three values (0, 1, 2) using three pointers. The same write-head intuition applies — the low pointer tracks the boundary for 0s and the high pointer tracks the boundary for 2s, with 1s accumulating in the middle.

Remove Element (LeetCode 27) is structurally identical to the overwrite version of Move Zeroes: overwrite all elements equal to val, then return the new length. Remove Duplicates from Sorted Array (LeetCode 26) uses the same slow/fast pointer template but keeps one copy of each duplicate rather than removing a specific value. All three share the same "write head advances only on keep" structure.

Quick Sort's partition step is the algorithmic ancestor of all these problems. It rearranges elements around a pivot, placing elements smaller than the pivot before it and larger elements after, exactly like the two-pointer partition. Understanding Move Zeroes as a special case of partition — where the pivot is 0 and all zeros go right — connects the interview problem to the foundational sorting algorithm. This insight often impresses interviewers when stated explicitly.