Move Zeroes

Move every 0 to the end of an array in place, keeping the other numbers in their order.

In an array of integers nums, move every 0 to the end, and keep the other numbers in the order they had. Change nums itself, without making a copy of the array.

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

The Idea

Picture five boxes in a row on a shelf, holding 0, 1, 0, 3 and 12. A 0 is an empty box. You want the full boxes at the front, in the same order as before, and the empty ones pushed to the back. For Example 1 that gives 1, 3, 12, followed by the two zeros.

The boxes cannot leave the shelf, though. The array has to be rearranged inside itself, with no second array to copy into. One way is to take out each 0, shift every number after it one place left, and put the 0 at the end. But then each 0 costs a pass over the rest of the array. Can every number reach its place in a single read of the array?

Think about where each non-zero number should end up. The first non-zero belongs at index 0, the second at index 1, and so on. So while reading the array from left to right, only one thing needs remembering: the index where the next non-zero belongs. Call it slow, and call the index being read fast. Both start at 0.

When fast reads a 0, nothing happens and fast moves on. When it reads a non-zero, that number is swapped with whatever sits at slow, and slow moves one place right. Look at the picture below.

The array 1, 0, 0, 3, 12 with slow at index 1 and fast at index 3. Swapping the 3 with the 0 at slow gives 1, 3, 0, 0, 12, and slow moves to index 2.

In the top row, labelled "before the swap", fast has already read 0, 1 and 0, and the 1 now sits at index 0. So slow is at index 1, the next place for a non-zero, and indexes 1 and 2 hold the zeros read so far. Now fast reads the 3 at index 3. Swapping it with the 0 at slow gives the row labelled "after the swap", 1, 3, 0, 0, 12, and slow moves to index 2.

So the array always has three parts: the non-zeros so far at the front, then the zeros already read, then the numbers fast has not read yet. Each swap adds one non-zero to the front part and moves one 0 to the back of the zeros. When fast reaches the end, the zeros fill the back of the array.

Two indexes that walk through an array in the same direction, one reading and one marking where to write, are a form of the two-pointer technique. Because one of them can only lag behind the other, they are often called slow and fast pointers.

Solution Approach

Turning that idea into code means settling three things: what to do with a non-zero, how the order of the numbers is kept, and what happens when there is no 0 to swap with.

Swapping a non-zero forward

What should happen when fast reads a non-zero? It belongs at nums[slow]. Every index from slow up to fast - 1 holds a 0, so when slow and fast differ, the number at slow is a 0. The swap puts the non-zero at slow and that 0 at fast, and nothing is lost.

The swap is also what makes one pass enough. Shifting the rest of the array left for every 0 can take about n steps per 0, where n is the length of the array. With many zeros, that grows like n². Here each number is read once and swapped at most once.

Keeping the order

Does the swap mix up the non-zeros? No. fast meets the non-zeros from left to right, and each one goes to the next free place at the front, so they arrive in the order they had. The zeros are all the same, so their order does not matter.

Arrays without a 0 to swap

What if the array has no zeros at all, like [1, 2, 3]? Then slow never falls behind fast, and each number is swapped with itself. The array stays as it was, so no special check is needed. [0] and an empty array need no special code either, because the loop finds nothing to move.

Java Solution

The method moveZeroes works in these steps:

  1. First, set slow to 0, the index where the next non-zero belongs.
  2. Read the array with a for loop, in which fast goes from 0 to the last index.
  3. When nums[fast] is not 0, swap it with nums[slow] through a temporary variable tmp, then move slow one place right. When it is 0, do nothing, and the loop moves fast on.
  4. When the loop ends, the non-zeros fill the front of nums in their old order, and the zeros fill the rest. The method returns nothing, because it has changed nums itself.

The main method runs both examples, an array with no zeros, one that starts with two zeros, one with a negative number and a repeated 4, and an empty array. A small helper, run, prints each array before and after the call.

Java
import java.util.Arrays;

public class MoveZeroes {

    public static void moveZeroes(int[] nums) {
        int slow = 0;                         // where the next non-zero belongs
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                int tmp = nums[slow];         // swap the non-zero forward;
                nums[slow] = nums[fast];      // a zero (if any) moves back
                nums[fast] = tmp;
                slow++;
            }
        }
    }

    static void run(int[] nums) {
        String before = Arrays.toString(nums);
        moveZeroes(nums);
        System.out.println(before + " -> " + Arrays.toString(nums));
    }

    public static void main(String[] args) {
        run(new int[] {0, 1, 0, 3, 12});
        run(new int[] {0});
        run(new int[] {1, 2, 3});
        run(new int[] {0, 0, 1});
        run(new int[] {4, 0, -5, 0, 0, 4});
        run(new int[] {});
    }
}

Running it prints:

Output
[0, 1, 0, 3, 12] -> [1, 3, 12, 0, 0]
[0] -> [0]
[1, 2, 3] -> [1, 2, 3]
[0, 0, 1] -> [1, 0, 0]
[4, 0, -5, 0, 0, 4] -> [4, -5, 4, 0, 0, 0]
[] -> []

Look at the fourth line: [0, 0, 1] becomes [1, 0, 0]. slow stays at index 0 while fast passes the two zeros, so the 1 at index 2 is swapped straight to the front, and the 0 from index 0 goes to index 2.

The fifth line turns [4, 0, -5, 0, 0, 4] into [4, -5, 4, 0, 0, 0]. The -5 counts as a non-zero like any other number, and the 4, -5, 4 at the front keep their old order. On the third line, [1, 2, 3] comes out unchanged after each number was swapped with itself, and the last line shows the empty array passing through without an error.

The original implementation, MoveZeroes.java, is on GitHub.

Complexity

The work is a single pass of fast over the array, with at most one swap per number.

  • Time: O(n), for an array of n numbers, because the for loop reads each of the n numbers once and does at most one swap of three assignments for each.
  • Space: O(1). The numbers are rearranged inside nums, and only slow, fast and tmp are used.

The same slow and fast pointers solve Remove Duplicates from Sorted Array, where slow marks the place for the next new value.