Move Zeroes (LeetCode 283)
You're given an integer array nums. Push every 0 toward the end of the array, but keep the non-zero values in their original relative order.
Note that this has to happen in-place — no copying into a second array.
Worked Examples
nums = [0,1,0,3,12][1,3,12,0,0]nums = [0][0]⚖️Formal Constraints & Bounds
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
Core Insight
Separating discovery of non-zeroes from zero-filling avoids expensive O(N^2) element shifting.
Real-World Scenario & Production Applications
Sparse array compaction, memory garbage collection compaction phases, and streaming event buffer filtering.
Subproblems & Recurrence Decomposition3 Phases
insert_pos tracks where the next non-zero value should be written, starting at index 0.
insert_pos = 0Step-by-Step Execution Trace Table
| Step | reader | nums[reader] | Action | nums State | writer |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 == 0 → skip | [0, 1, 0, 3, 12] | 0 |
| 2 | 1 | 1 | 1 != 0 → nums[0]=1, writer++ | [1, 1, 0, 3, 12] | 1 |
| 3 | 2 | 0 | 0 == 0 → skip | [1, 1, 0, 3, 12] | 1 |
| 4 | 3 | 3 | 3 != 0 → nums[1]=3, writer++ | [1, 3, 0, 3, 12] | 2 |
| 5 | 4 | 12 | 12 != 0 → nums[2]=12, writer++ | [1, 3, 12, 3, 12] | 3 |
| Fill | 3..4 | — | Zero-fill from writer=3 to end | [1, 3, 12, 0, 0] | 3 |
| 1 | writer = 0 |
| 2 | for reader in range(len(nums)): |
| 3 | if nums[reader] != 0: |
| 4 | nums[writer] = nums[reader] |
| 5 | writer += 1 |
| 6 | for i in range(writer, len(nums)): |
| 7 | nums[i] = 0 |
| 8 | return nums |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Moving zeroes to the end of an array while maintaining the relative order of non-zero elements is the canonical Slow/Fast Reader-Writer Partitioning pattern. Rather than shifting elements backward upon discovering a zero ( time), we decouple the role of scanning elements from the role of writing validated data. The writer pointer w maintains the frontier of clean non-zero elements, while the reader pointer r traverses ahead to inspect candidates.
🏟️ The Analogy: The Snowplow on a Highway
Imagine a snowplow (r) driving down a multi-lane highway covered in snowdrifts (0s) and stranded cars (non-zero numbers). Behind the plow follows a tow truck (w). Whenever the plow finds a working car, it radios the tow truck, which parks it at the earliest open lane slot (w). Once the highway has been inspected, all working cars are packed neatly at the beginning of the road; the rest of the highway behind them is simply paved over with asphalt (0s).
🔑 Why It Works
By swapping nums[w] and nums[r] instead of performing a two-pass overwrite, the algorithm automatically moves zeros backward without requiring a second zero-fill loop! When w == r, the element swaps with itself (a no-op). When zeroes have been encountered, w lags behind r, pointing precisely to the leftmost zero waiting to receive the next non-zero car.
Overwriting non-zero values with zero prematurely: When using separate read and write pointers, writing
nums[writer] = 0during the initial compaction pass will overwrite unprocessed non-zero values ahead of it. Only fill remaining slots with zeros after the reader pass finishes.Redundant self-assignment when no zeros have been encountered: If all initial elements are non-zero,
reader == writer. Writingnums[writer] = nums[reader]or swapping on every step does redundant memory writes. Guard withif reader != writer:.Incomplete zero-fill at array tail: After moving all non-zero elements to
[0..writer-1], forgetting the second passwhile writer < len(nums): nums[writer] = 0; writer += 1leaves stale duplicate values at the tail.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
In-place array filtering + relative ordering preservation + constant space requirement.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: nums[0..writer-1] contains all non-zero elements encountered so far in relative order.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using expensive nested array deletion / splice operations: O(N^2) trap.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I iterate with a reader pointer. When nums[reader] is non-zero, I write it to nums[writer] and increment writer. After the loop, I fill indices from writer to the end with zeroes. Runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Fast pointer scans array; on non-zero, swaps with slow pointer or writes to slow pointer index and advances. Single linear pass.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Modifies array in-place with two scalar pointer indices.
T(N) = O(N)
Derivation Progression
for r ∈ [0, N-1]
Right pointer traverses the array from 0 to N-1.
nums[l], nums[r] = nums[r], nums[l]
Maintains invariant that nums[0..l-1] contains non-zero elements in original order.
N iterations × O(1) = O(N)
Every element is inspected once and swapped at most once.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(1) Two scalar pointers
O(1) In-place array modification
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "move all 0's to the end", "maintain relative order of non-zero elements", "in-place without copying the array". Compaction and snowplow pattern: all non-zero elements must be compacted into the prefix, leaving zeros trailing.
. Time budget single pass, auxiliary space .
Overwriting elements instead of swapping (which requires a second loop to fill zeros). When array has no zeros, slow == fast; swapping nums[slow], nums[fast] is an identity operation that safely preserves order.
Move Zeroes (LeetCode 283)
You're given an integer array nums. Push every 0 toward the end of the array, but keep the non-zero values in their original relative order.
Note that this has to happen in-place — no copying into a second array.
Worked Examples
nums = [0,1,0,3,12][1,3,12,0,0]nums = [0][0]⚖️Formal Constraints & Bounds
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
Core Insight
Separating discovery of non-zeroes from zero-filling avoids expensive O(N^2) element shifting.
Real-World Scenario & Production Applications
Sparse array compaction, memory garbage collection compaction phases, and streaming event buffer filtering.
Subproblems & Recurrence Decomposition3 Phases
insert_pos tracks where the next non-zero value should be written, starting at index 0.
insert_pos = 0Step-by-Step Execution Trace Table
| Step | reader | nums[reader] | Action | nums State | writer |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 == 0 → skip | [0, 1, 0, 3, 12] | 0 |
| 2 | 1 | 1 | 1 != 0 → nums[0]=1, writer++ | [1, 1, 0, 3, 12] | 1 |
| 3 | 2 | 0 | 0 == 0 → skip | [1, 1, 0, 3, 12] | 1 |
| 4 | 3 | 3 | 3 != 0 → nums[1]=3, writer++ | [1, 3, 0, 3, 12] | 2 |
| 5 | 4 | 12 | 12 != 0 → nums[2]=12, writer++ | [1, 3, 12, 3, 12] | 3 |
| Fill | 3..4 | — | Zero-fill from writer=3 to end | [1, 3, 12, 0, 0] | 3 |
| 1 | writer = 0 |
| 2 | for reader in range(len(nums)): |
| 3 | if nums[reader] != 0: |
| 4 | nums[writer] = nums[reader] |
| 5 | writer += 1 |
| 6 | for i in range(writer, len(nums)): |
| 7 | nums[i] = 0 |
| 8 | return nums |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Moving zeroes to the end of an array while maintaining the relative order of non-zero elements is the canonical Slow/Fast Reader-Writer Partitioning pattern. Rather than shifting elements backward upon discovering a zero ( time), we decouple the role of scanning elements from the role of writing validated data. The writer pointer w maintains the frontier of clean non-zero elements, while the reader pointer r traverses ahead to inspect candidates.
🏟️ The Analogy: The Snowplow on a Highway
Imagine a snowplow (r) driving down a multi-lane highway covered in snowdrifts (0s) and stranded cars (non-zero numbers). Behind the plow follows a tow truck (w). Whenever the plow finds a working car, it radios the tow truck, which parks it at the earliest open lane slot (w). Once the highway has been inspected, all working cars are packed neatly at the beginning of the road; the rest of the highway behind them is simply paved over with asphalt (0s).
🔑 Why It Works
By swapping nums[w] and nums[r] instead of performing a two-pass overwrite, the algorithm automatically moves zeros backward without requiring a second zero-fill loop! When w == r, the element swaps with itself (a no-op). When zeroes have been encountered, w lags behind r, pointing precisely to the leftmost zero waiting to receive the next non-zero car.
Overwriting non-zero values with zero prematurely: When using separate read and write pointers, writing
nums[writer] = 0during the initial compaction pass will overwrite unprocessed non-zero values ahead of it. Only fill remaining slots with zeros after the reader pass finishes.Redundant self-assignment when no zeros have been encountered: If all initial elements are non-zero,
reader == writer. Writingnums[writer] = nums[reader]or swapping on every step does redundant memory writes. Guard withif reader != writer:.Incomplete zero-fill at array tail: After moving all non-zero elements to
[0..writer-1], forgetting the second passwhile writer < len(nums): nums[writer] = 0; writer += 1leaves stale duplicate values at the tail.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
In-place array filtering + relative ordering preservation + constant space requirement.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: nums[0..writer-1] contains all non-zero elements encountered so far in relative order.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using expensive nested array deletion / splice operations: O(N^2) trap.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I iterate with a reader pointer. When nums[reader] is non-zero, I write it to nums[writer] and increment writer. After the loop, I fill indices from writer to the end with zeroes. Runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Fast pointer scans array; on non-zero, swaps with slow pointer or writes to slow pointer index and advances. Single linear pass.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Modifies array in-place with two scalar pointer indices.
T(N) = O(N)
Derivation Progression
for r ∈ [0, N-1]
Right pointer traverses the array from 0 to N-1.
nums[l], nums[r] = nums[r], nums[l]
Maintains invariant that nums[0..l-1] contains non-zero elements in original order.
N iterations × O(1) = O(N)
Every element is inspected once and swapped at most once.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(1) Two scalar pointers
O(1) In-place array modification
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "move all 0's to the end", "maintain relative order of non-zero elements", "in-place without copying the array". Compaction and snowplow pattern: all non-zero elements must be compacted into the prefix, leaving zeros trailing.
. Time budget single pass, auxiliary space .
Overwriting elements instead of swapping (which requires a second loop to fill zeros). When array has no zeros, slow == fast; swapping nums[slow], nums[fast] is an identity operation that safely preserves order.