easy
Move Zeroes
Given an integer array, move all zeros to the end while preserving the relative order of the non-zero elements. Do it in place without allocating a second array.
Constraints
- 1 ≤ n ≤ 10^4
- -2^31 ≤ nums[i] ≤ 2^31 - 1
Examples
in: nums = [0,1,0,3,12]
out: [1,3,12,0,0]
Recognition clues
- Stable in-place partition into two groups
- A write pointer for the next non-zero slot
- Order of one group must be preserved
Pattern
Two PointersWhen order gives you a way to decide which of two ends to move, you can replace an O(n^2) double loop by a single pass. Opposite-direction pointers exploit sortedness (move the side that must change); same-direction pointers maintain a "written so far" prefix for in-place compaction.
Solution
Maintain w, the index where the next non-zero value should go. Scan with r; whenever nums[r] is non-zero, swap it with nums[w] and advance w. Every non-zero element is placed at the earliest free position in scan order, preserving relative order, and all positions from w onward end up zero.
time O(n)space O(1)
Alternative approaches
- Counting zeros and overwriting is equivalent. A general non-stable partition (like Lomuto) would be wrong here because it reorders the non-zero elements.
Code it yourself
Solve in
Hints: