Back to solutions

Move Zeroes

EasyArrays

Shift every zero to the end while keeping the order of the non-zero values.

Open problem
Constraints
  • 1 <= n <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

Two pointers (stable partition)

Time O(n)Space O(1)

Keep an `insert` pointer marking where the next non-zero value belongs. Scan with i; whenever nums[i] is non-zero, swap it into the insert slot and advance insert. Non-zeros stay in order and zeros are pushed to the back, all in one pass.

Key terms
two pointers:
Using two indices that move through the array at different rates to rearrange it in place.
insert pointer (write index):
The position where the next non-zero element should be placed.
stable:
The relative order of equal/kept elements is preserved after rearranging.
void moveZeroes(vector<int>& nums) {
    int insert = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (nums[i] != 0) swap(nums[insert++], nums[i]);
    }
}
Step by step
  1. Set insert = 0; it tracks the front region that already holds non-zeros in order.
  2. Walk i across the array.
  3. If nums[i] is non-zero, swap nums[insert] and nums[i], then increment insert.
  4. Zeros are skipped, so they accumulate after the insert boundary.
  5. When the scan ends, positions [0, insert) are the original non-zeros in order and the rest are zeros.