Part 2 · Problems · Two pointers
Move Zeroes
#283 · Easy · LeetCode
Move all zeros to the end in place, keeping the order of the other numbers.
[0,1,0,3,12] -> [1,3,12,0,0]
Ask before coding
- In place?
- Keep relative order?
Hint
A reader pointer and a writer pointer.
Approach
w is where the next non-zero goes. Read every element. When it's non-zero, swap it into w and move w forward.
Time O(n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function moveZeroes(nums) {
let w = 0; // next slot for a non-zero
for (let r = 0; r < nums.length; r++) {
if (nums[r] !== 0) {
[nums[w], nums[r]] = [nums[r], nums[w]];
w++;
}
}
}Traps
- Removing with splice inside a loop is O(n²) and skips elements.
Say out loud: Classic read pointer, write pointer. Swapping keeps the zeros moving to the back.