Command Palette

Search for a command to run...

Hectal
Problem 6.2 · Two PointersEasy

Move Zeroes

PatternTwo Pointers: Read and Write

What it teaches: Read/write pointers keep the non-zero elements in order at the front; the rest is filled with zeros.

Practise it on judges as “Move Zeroes”.

The problem

Move all 0s in nums to the end while keeping the relative order of the non-zero elements. Do it in place.

Example 1

Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Example 2

Input: nums = [0]
Output: [0]

Constraints

  • 1 ≤ nums.length ≤ 10⁴
  • In place

Pattern clues in the wording

  • → In-place filter that keeps order
  • → "Move X to the end"

These clues point to Two Pointers: Read and Write: A fast pointer reads every element and a slow pointer marks where the next kept element should be written.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public void moveZeroes(int[] nums) {
        int write = 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [0,1,0,3,12]
[1,3,12,0,0]
2
nums = [0]
[0]

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Optimal: swap non-zeros forward · O(n)
1

Optimal: swap non-zeros forward

Time O(n) Space O(1)

write marks the next spot for a non-zero. When nums[read] is non-zero, swap it with nums[write] and advance write. Zeros naturally collect after write.

▶ Dry run: Swapping non-zeros to the frontnums = [0, 1, 0, 3, 12]
0
0
↑w↑r
1
1
0
2
3
3
12
4

Step 1/5nums[0] is 0: skip.

Approach 1
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++;
            }
        }
    }
}

Verdict: One pass, order preserved.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No zeros
  • All zeros
  • Zeros only at the end

Mistakes people make

  • Swapping zeros with the last element (breaks the order of non-zeros).
  • Creating a new array (not in place).

Interview

Follow-up questions

How do you minimise the number of writes?