Difficulty: Easy Pattern: Two Pointers LeetCode: https://leetcode.com/problems/move-zeroes/
Given an integer array nums, move all 0’s to the end of it in-place
while maintaining the relative order of the non-zero elements. You must do this
without making a copy of the array, and the operation should run in O(n) time.
Signature:
void moveZeroes(int[] nums)
Examples (verbatim from LeetCode):
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Input: nums = [0]
Output: [0]
Picture sorting a hand of cards: you want all the real cards pushed to the front in their original order, and every empty slot pushed to the back. You look at the cards one by one from left to right; each time you spot a real card, you place it into the next free front slot; blanks you simply skip past. When you finish scanning, any slot you never filled is a leftover blank, so you stamp it as empty. That mental model – a reading finger and a slower writing finger – is the second flavor of two pointers, called fast/slow (or read/write). Both start at the left, but they advance at different rates.
Let’s watch it on the tiniest case, nums = [0, 1, 2]:
read=0 sees 0 – a blank, skip it. write stays at 0.read=1 sees 1 – a real value. Copy it into slot write=0, then bump
write to 1. Array is now [1, 1, 2].read=2 sees 2 – real. Copy into slot write=1, bump write to 2. Array
is [1, 2, 2].write=2 onward were never filled – stamp them with
0. Array becomes [1, 2, 0].The general rule falls straight out of that walk: one loop copies every non-zero
into the next write slot; a second short loop stamps zeros into everything
write did not reach. Why does the relative order of the non-zeros survive?
Because write only ever moves forward and never overtakes read – each kept
value lands in a slot at or before its original position, so it can never leapfrog
a value that came after it.
This is an in-place solution: we reuse the input array and keep only two index variables, so the extra memory is O(1). (The other two-pointer flavor – one finger at each end, moving inward – is what Valid Palindrome and Squares of a Sorted Array use; both flavors share the same core idea of “two indices, moved by a rule, no nested loop”.)
Pause and pick before expanding. A wrong first guess teaches more than a fast right one.
Q1 (recall). In the fast/slow pair, when does the write pointer advance?
read sees a non-zero valuereadread sees a zeroQ2 (comprehend). Why does the relative order of the non-zero elements survive the move?
write only ever moves forward and never overtakes read, so each kept value lands at or before its original position, in orderfunction moveZeroes(nums):
set write to first index
for read from first index to last index:
if nums[read] is not zero:
copy nums[read] into nums[write]
advance write
# everything from write onward is now stale -> fill with zeroes
while write <= last index:
set nums[write] to zero
advance write
class Solution {
public void moveZeroes(int[] nums) {
int write = 0;
for (int read = 0; read < nums.length; read++) {
if (nums[read] != 0) {
nums[write] = nums[read];
write++;
}
}
while (write < nums.length) {
nums[write] = 0;
write++;
}
}
}
write only advances on a kept element, so after the loop [0, write) holds
every non-zero value in its original order. The trailing while then pads the
rest with zeroes. We write unconditionally with nums[write] = nums[read]
rather than swapping: overwriting is fine because every value is preserved
(whatever was at write has already been copied forward, or is a zero we do
not need). This keeps the code branch-free and obviously O(n). The space cost
is O(1) — we reuse the input array and use only two index variables.
Time: O(n) -- the read loop visits each element once; the zero-fill loop visits at most the rest.
Space: O(1) -- in-place; no auxiliary array, just the `write` index.
Step-by-step on nums = [0,1,0,3,12]. We track read, write, and the array
after each read iteration.
| read | nums[read] | write | action | nums after |
|---|---|---|---|---|
| 0 | 0 | 0 | zero -> skip | [0,1,0,3,12] |
| 1 | 1 | 0 | copy nums[1]->nums[0]; write=1 | [1,1,0,3,12] |
| 2 | 0 | 1 | zero -> skip | [1,1,0,3,12] |
| 3 | 3 | 1 | copy nums[3]->nums[1]; write=2 | [1,3,0,3,12] |
| 4 | 12 | 2 | copy nums[4]->nums[2]; write=3 | [1,3,12,3,12] |
| (fill) | - | 3 | nums[3]=0; write=4 | [1,3,12,0,12] |
| (fill) | - | 4 | nums[4]=0; write=5 | [1,3,12,0,0] |
Final nums = [1,3,12,0,0]. The non-zero prefix [1,3,12] is in original
order, and the tail [0,0] holds exactly the two zeroes that were skipped.
Q1 (apply). Trace nums = [2,0,4,0,5]. What is the array after the algorithm runs?
[2,4,5,0,0][2,4,5,5,0][0,0,2,4,5]Q2 (analyze). What goes wrong if the final zero-fill loop starts at index 0 instead of at write?
Q3 (transfer). How would you adapt this to “remove all copies of a value k in-place and return the new length” (LC 27)?
if (read != write) guard is a
premature optimisation that obscures the simple write-then-fill flow.write.read < write condition would skip the tail.void; the answer is left in the
mutated input array.