Sweaty Imposter

Move Zeroes

EasyTwo PointersNeetCode 150JuniorOpen on LeetCodeUpdated

You're given an integer array nums. Move every 0 to the end of the array while keeping the non-zero elements in their original relative order. Do it in place: modify nums directly without making a copy of the array, and return nothing.

Examples

nums = [0,1,0,3,12] returns [1,3,12,0,0]

The non-zero values 1, 3 and 12 keep their order and slide to the front, and the two zeros fill the last two slots.

nums = [0] returns [0]

A single zero is already at the end, so nothing changes.

Constraints

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

Hints

Hint 1

Instead of moving the zeros, think about where each non-zero value should end up.

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Keep a write index for where the next non-zero value belongs, starting at 0. Scan with read, and whenever nums[read] is non-zero, swap it into position write and advance write. Everything before write is then the non-zero values in their original order, and everything from write up to read is zeros, so when the scan ends every zero sits at the back. Each element moves at most once.

Time

O(n)

Space

O(1)

Pitfall

Removing each zero and appending it, or shifting the rest left, costs O(n) per zero and O(n^2) overall. Swapping each zero with the last element is fast but scrambles the order of the non-zero values.

Solutions

class Solution {
    public void moveZeroes(int[] nums) {
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (nums[read] != 0) {
                int tmp = nums[write];
                nums[write] = nums[read];
                nums[read] = tmp;
                write++;
            }
        }
    }
}
Drill This