Move Zeroes

Easy Arrays & Hashing Two Pointer Original on LeetCode

Move Zeroes is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (one-pass swap), runs in O(n) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from extra array up.

Problem

Given an integer array nums, move every 0 to the end of the array while keeping the non-zero elements in the same relative order they started in.

Do this in place, without making a copy of the array. The function returns nothing; nums is checked after the call.

Examples

Example 1

Input
nums = [4, 0, 0, 7, 2, 0, 9]
Output
[4, 7, 2, 9, 0, 0, 0]
Why
The non-zero values keep their order 4, 7, 2, 9 and the three zeros collect at the end.

Example 2

Input
nums = [0, -3, 0]
Output
[-3, 0, 0]
Why
Negative numbers are non-zero too, so -3 moves to the front.

Example 3

Input
nums = [5, 1]
Output
[5, 1]
Why
With no zeros the array is left exactly as it was.

Constraints

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • Modify nums in place; the function returns nothing.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Extra arrayO(n)O(n)
Compact, then fill with zerosO(n)O(1)
Optimal (one-pass swap)O(n)O(1)

1Extra array

TimeO(n)Two linear passes.
SpaceO(n)The temporary array has n slots.

Copy the non-zero values into a new array in order, leave the rest as zeros, then copy the new array back into nums.

  1. Create tmp of length n filled with 0.
  2. Walk nums; append every non-zero value to tmp at position k, then k++.
  3. Copy tmp back into nums.
class Solution {
    public void moveZeroes(int[] nums) {
        int[] tmp = new int[nums.length];
        int k = 0;
        for (int x : nums) {
            if (x != 0) tmp[k++] = x;
        }
        System.arraycopy(tmp, 0, nums, 0, nums.length);
    }
}

2Compact, then fill with zeros

TimeO(n)One pass to compact, one pass over the tail to zero it.
SpaceO(1)Only the write pointer.

Use a write pointer inside nums itself. Every non-zero value is written at the write pointer, which then advances. After the pass, everything from the write pointer to the end must be zero, so fill it.

  1. write = 0.
  2. For each value x in nums: if x != 0, nums[write++] = x.
  3. For i from write to n - 1, set nums[i] = 0.
class Solution {
    public void moveZeroes(int[] nums) {
        int write = 0;
        for (int x : nums) {
            if (x != 0) nums[write++] = x;
        }
        while (write < nums.length) nums[write++] = 0;
    }
}

3Optimal (one-pass swap)

TimeO(n)A single pass with at most one swap per element.
SpaceO(1)Two indices and a temporary for the swap.

Same write pointer, but swap nums[read] with nums[write] whenever nums[read] is non-zero. Everything before write is the finished non-zero prefix, everything between write and read is zero, so each swap moves a non-zero value forward and a zero backward in a single pass. It also does no writes at all when there are no zeros.

  1. write = 0.
  2. For read from 0 to n - 1: if nums[read] != 0, swap nums[read] and nums[write] (skip when they are the same index), then write++.
class Solution {
    public void moveZeroes(int[] nums) {
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (nums[read] != 0) {
                if (read != write) {
                    int t = nums[read];
                    nums[read] = nums[write];
                    nums[write] = t;
                }
                write++;
            }
        }
    }
}

Edge cases to test

  • No zeros at all
  • All zeros
  • A single element
  • Zeros already at the end
  • Negative values (only 0 counts as zero)

Hints

Hint 1

Think of the non-zero values as being written into a prefix of the array, in their original order.

Hint 2

Keep a pointer to the next slot where a non-zero value should go. What happens to the slots after the last non-zero value?

Hint 3

Swapping instead of overwriting lets you do it in one pass: the zero that was in the slot moves to where the non-zero value came from.

FAQ

What is the best time complexity for Move Zeroes?

Optimal (one-pass swap) runs in O(n) time and O(1) extra space. A single pass with at most one swap per element.

Which pattern does Move Zeroes use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Move Zeroes?

Yes. Extra array takes O(n) time and O(n) space. Copy the non-zero values into a new array in order, leave the rest as zeros, then copy the new array back into nums.

Which edge cases should I test for Move Zeroes?

No zeros at all; All zeros; A single element; Zeros already at the end; Negative values (only 0 counts as zero).