Move Zeroes
Problem
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. This must be done in-place without making a copy of the array.
- 1 ≤ nums.length ≤ 10⁴
- −2³¹ ≤ nums[i] ≤ 2³¹ - 1
Example
nums = [0,1,0,3,12][1,3,12,0,0]A naive approach might repeatedly swap zeros with the next non-zero element, resulting in many operations. Instead, the algorithm uses two pointers: one to scan through the array (right pointer) and one to track the position to place the next non-zero element (left pointer). As it iterates, it overwrites the left pointer's position with the current non-zero element and increments the left pointer. This effectively compacts all non-zero elements at the front in their original order.
Approach
Straightforward Solution
A brute-force approach swaps every zero with the next non-zero element found, which can lead to O(n^2) time complexity due to repeated swaps.
Core Observation
The relative order of non-zero elements must be preserved, and zeros must be moved to the end. This implies a stable partition of the array into non-zero and zero elements.
Path to Optimal
The key insight is to use two pointers: one scanning through the array and one marking the position to place the next non-zero element. By overwriting elements at the left pointer with non-zero elements found by the right pointer, the algorithm compacts non-zero elements at the front in a single pass. After this pass, all remaining positions from the left pointer to the end are set to zero.
Optimal Approach
Iterate through the array with a right pointer. For each non-zero element, write it to the position indicated by the left pointer and increment the left pointer. After processing all elements, fill the rest of the array from the left pointer to the end with zeros. This approach guarantees O(n) time and O(1) auxiliary space.
Time
O(n)
The algorithm makes a single pass through the array with the right pointer, and a second pass to fill zeros from the left pointer to the end, both linear operations.
Space
O(1)
All operations are done in-place with only two integer pointers used, requiring constant auxiliary space.
Pattern Spotlight
Two Pointers (Stable Partition)
Use one pointer to scan all elements and another to track the position to place the next valid element, enabling a stable partition of the array in a single pass without extra space.
Solution
| 1 | class Solution:
|
| 2 | def moveZeroes(self, nums: List[int]) -> None:
|
| 3 | l = 0
|
| 4 | for r in range(len(nums)):
|
| 5 | if nums[r] != 0:
|
| 6 | nums[l] = nums[r]
|
| 7 | l += 1
|
| 8 |
|
| 9 | while l < len(nums):
|
| 10 | nums[l] = 0
|
| 11 | l += 1 |
| 1 | import java.util.List; |
| 2 | |
| 3 | public class Solution { |
| 4 | public void moveZeroes(int[] nums) { |
| 5 | int l = 0; |
| 6 | for (int r = 0; r < nums.length; r++) { |
| 7 | if (nums[r] != 0) { |
| 8 | nums[l] = nums[r]; |
| 9 | l++; |
| 10 | } |
| 11 | } |
| 12 | while (l < nums.length) { |
| 13 | nums[l] = 0; |
| 14 | l++; |
| 15 | } |
| 16 | } |
| 17 | } |
| 1 | #include <vector> |
| 2 | using namespace std; |
| 3 | |
| 4 | class Solution { |
| 5 | public: |
| 6 | void moveZeroes(vector<int>& nums) { |
| 7 | int l = 0; |
| 8 | for (int r = 0; r < (int)nums.size(); r++) { |
| 9 | if (nums[r] != 0) { |
| 10 | nums[l] = nums[r]; |
| 11 | l++; |
| 12 | } |
| 13 | } |
| 14 | while (l < (int)nums.size()) { |
| 15 | nums[l] = 0; |
| 16 | l++; |
| 17 | } |
| 18 | } |
| 19 | }; |
| 1 | var moveZeroes = function(nums) { |
| 2 | let l = 0; |
| 3 | for (let r = 0; r < nums.length; r++) { |
| 4 | if (nums[r] !== 0) { |
| 5 | nums[l] = nums[r]; |
| 6 | l++; |
| 7 | } |
| 8 | } |
| 9 | while (l < nums.length) { |
| 10 | nums[l] = 0; |
| 11 | l++; |
| 12 | } |
| 13 | }; |
Step-by-Step Solution
Track Position to Place Next Non-Zero Element
| 3 | l = 0
|
Objective
To maintain a pointer that marks the next index where a non-zero element should be placed.
Key Insight
The left pointer acts as a boundary between processed non-zero elements and the rest of the array. By incrementing it only when a non-zero element is found, the algorithm ensures that all non-zero elements are compacted at the front in their original order without gaps.
Interview Quick-Check
Core Logic
The left pointer tracks the position to overwrite with the next non-zero element, enabling stable compaction.
State & Boundaries
The left pointer starts at 0 and only moves forward when a non-zero element is placed, ensuring no overwriting of unprocessed elements.
Common Pitfalls & Bugs
Failing to increment the left pointer only on non-zero elements leads to incorrect overwriting and loss of order.
Iterate Through Array and Overwrite Non-Zero Elements
| 4 | for r in range(len(nums)):
|
| 5 | if nums[r] != 0:
|
| 6 | nums[l] = nums[r]
|
| 7 | l += 1
|
Objective
To scan the array with a right pointer and copy non-zero elements to the left pointer's position.
Key Insight
The Read Pointer (r) scans for valid data, while the Write Pointer (l) waits at the next open slot. This filtering creates a 'gap' between the pointers, allowing us to compact the array in-place without using extra memory
Interview Quick-Check
Core Logic
The right pointer scans every element, and non-zero elements are copied to the left pointer's position, which advances accordingly.
State & Boundaries
The loop runs from 0 to len(nums)-1, ensuring all elements are processed.
Common Pitfalls & Bugs
Not checking for non-zero elements before copying can overwrite zeros prematurely, breaking the algorithm.
Fill Remaining Positions with Zeros
| 9 | while l < len(nums):
|
| 10 | nums[l] = 0
|
| 11 | l += 1 |
Objective
To overwrite the remaining elements from the left pointer to the end of the array with zeros.
Key Insight
After all non-zero elements have been moved forward, the remaining positions must be set to zero to complete the stable partition. This step ensures that zeros are grouped at the end without disturbing the order of non-zero elements.
Interview Quick-Check
Core Logic
Filling zeros from the left pointer to the end finalizes the in-place stable partition.
State & Boundaries
The while loop continues until the left pointer reaches the array's length, ensuring all trailing positions are zeroed.
Common Pitfalls & Bugs
Failing to fill zeros after moving non-zero elements leaves residual non-zero values in the tail.
Line Analysis
This solution has 1 Critical line interviewers watch for.
nums[l] = nums[r]Overwrite the element at the left pointer with the current non-zero element.
We write the value found by the Read pointer into the compacted zone. Overwriting is preferred over swapping here because it reduces total memory operations (1 write vs 3 assignments).
l = 0Initialize the left pointer to track the position for the next non-zero element.
This pointer marks the boundary where the next non-zero element should be placed, enabling stable compaction of non-zero elements at the front.
l += 1Increment the left pointer after placing a non-zero element.
Advancing the left pointer ensures the next non-zero element is placed in the correct subsequent position, maintaining order.
nums[l] = 0Set the current position to zero.
Explicitly overwriting with zero guarantees that all trailing elements are zeros, as required by the problem.
if nums[r] != 0:Check if the current element is non-zero.
This condition filters out zeros, ensuring only non-zero elements are moved forward, preserving their order.
while l < len(nums):Start filling zeros from the left pointer to the end of the array.
This loop ensures that all remaining positions after the last non-zero element are set to zero, completing the stable partition.
l += 1Increment the left pointer to continue filling zeros.
Moving the pointer forward ensures all positions from the last non-zero element to the end are zeroed.
for r in range(len(nums)):Iterate through the array with the right pointer.
The right pointer scans every element in order, ensuring all elements are processed exactly once.
Test Your Understanding
Why does overwriting elements at the left pointer with non-zero elements from the right pointer preserve the relative order of non-zero elements?
Because the right pointer scans elements in order, and each non-zero element is written sequentially at the left pointer, which only moves forward, preserving the original order of non-zero elements.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Move Zeroes from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Move Zeroes drill