FAANGPrep Sprint
Move Zeroes
Shift every 0 in the integer array nums to the back, in place, keeping the non-zero values in their original order.
Examples
Input:nums = [0,1,0,3,12]
Output:[1,3,12,0,0]
Explain:
Non-zero elements are 1, 3, 12. They stay in that order. The 0s go to the end.
Input:nums = [0]
Output:[0]
Problem Understanding
We need to push all 0s to the right side of the array.
Constraints:
- In-place: You cannot copy the valid numbers to a new array. You must do it inside
nums. - Relative Order: If
1comes before3originally, it must stay that way. - Minimize Operations: Ideally O(n) time.
Algorithm Strategy
We can use the Two Pointers technique to partition the array.
leftpointer: Tracks the position where the next non-zero element should go.rightpointer: Scans the array to find non-zero elements.
Logic:
- Iterate through the array with
right. - If
nums[right]is non-zero, we want to place it atnums[left]. - Swap
nums[left]andnums[right]. Thenleft++. - If
nums[right]is zero, just continue scanning (right++).
Interactive Visualization
L WRITES · R READS
WRITE AT 0
L
0
0
1
1
0
2
3
3
12
4
Write L
0
Read R
—
nums[R]
—
left marks where the next non-zero value goes; it starts at 0
Next
right reads nums[0] = 0
Array
Watch how L waits for a non-zero value, and R finds it.