Move the zeros to the end
Given an integer array nums, move every 0 to the end while keeping the other values in
their original relative order. Do it in place with O(1) extra memory, and return the array.
Examples
| Input | Output | Why |
|---|---|---|
nums = [0, 1, 0, 3, 12] | [1, 3, 12, 0, 0] | |
nums = [4, 2, 7] | [4, 2, 7] | No zeros: nothing moves. |
Constraints
- 1 ≤ n ≤ 10⁴
- −2³¹ ≤ nums[i] ≤ 2³¹ − 1
Hints
Hint 1
Copying the non-zero values to a new array and padding with zeros is easy. How would you do it in the same array?
Hint 2
Keep a write position w: the next non-zero value goes there. Read the array from left to right.
Hint 3
Swap each non-zero value into position w and advance w. The zeros drift right as values are swapped past them.
Where people lose marks
- Swapping adjacent zeros with each other repeatedly, which is O(n²) for an input such as many zeros followed by values.
- Using a partition that does not keep order (swapping with the far end): the non-zero values come out scrambled.
Dry run on [0,4,0,0,7,2]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 8nums00w/r4102037425w0
w marks where the next non-zero value goes; r reads every element.
-
Step 2 / 8nums00w/r4102037425w0r0
nums[0] = 0: leave it; the reader moves on.
-
Step 3 / 8nums40w01r02037425w1r1
nums[1] is non-zero: swap it to position 0, then w = 1.
-
Step 4 / 8nums4001w02r037425w1r2
nums[2] = 0: leave it; the reader moves on.
-
Step 5 / 8nums4001w0203r7425w1r3
nums[3] = 0: leave it; the reader moves on.
-
Step 6 / 8nums4071w020304r25w2r4
nums[4] is non-zero: swap it to position 1, then w = 2.
-
Step 7 / 8nums407122w030405rw3r5
nums[5] is non-zero: swap it to position 2, then w = 3.
-
Step 8 / 8nums407122030405w3
Done: the first 3 positions hold the non-zero values in order, and the rest are zeros.
How to think about it
Two pointers move in the same direction. The reader r visits every index; the writer
w marks the first position not yet filled with a non-zero value. The invariant is that
nums[0..w) holds the non-zero values seen so far, in their original order, and
nums[w..r) holds only zeros.
When nums[r] is non-zero, swap it with nums[w] and advance w. Swapping
rather than copying means the zero that was at w moves to r, so when the reader reaches
the end the zeros are already in place. The same reader-and-writer loop removes duplicates, filters values, and
partitions arrays.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def move_zeros(nums):
w = 0 # nums[:w] holds the non-zero values so far
for r in range(len(nums)):
if nums[r] != 0:
nums[w], nums[r] = nums[r], nums[w]
w += 1
return nums#include <vector>
#include <utility>
std::vector<int> solve(std::vector<int> nums) {
size_t w = 0; // nums[0..w) holds the non-zero values so far
for (size_t r = 0; r < nums.size(); ++r)
if (nums[r] != 0) std::swap(nums[w++], nums[r]);
return nums;
}class Solution {
public int[] moveZeros(int[] nums) {
int w = 0; // nums[0..w) holds the non-zero values so far
for (int r = 0; r < nums.length; r++) {
if (nums[r] != 0) { int t = nums[w]; nums[w] = nums[r]; nums[r] = t; w++; }
}
return nums;
}
}function moveZeros(nums) {
let w = 0; // nums[0..w) holds the non-zero values so far
for (let r = 0; r < nums.length; r++) {
if (nums[r] !== 0) { [nums[w], nums[r]] = [nums[r], nums[w]]; w++; }
}
return nums;
}fn solve(nums: &[i64]) -> Vec<i64> {
let mut v = nums.to_vec();
let mut w = 0; // v[..w] holds the non-zero values so far
for r in 0..v.len() {
if v[r] != 0 { v.swap(w, r); w += 1; }
}
v
}-- Lists cannot be changed in place, so the stable split is written directly:
-- the non-zero values in order, then the zeros.
solve :: [Int] -> [Int]
solve xs = filter (/= 0) xs ++ filter (== 0) xs
Variants to try
- Minimise writes: copy non-zero values forward without swapping, then fill the tail with zeros. Each position is written at most once.
- Move every value equal to k to the end and return how many are not equal to k.
Next problems
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minPair with a given sum in a sorted array
The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.
Open the problem →Write a solution and run it against the real test table.
Keep going
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minPair with a given sum in a sorted array
The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.