Move Zeroes to the End

Given an array of integers, move all the zeros to the end while keeping the relative order of the non-zero elements. Do it in place.

LeetCode: 283. Move Zeroes

Example

Text

Input:  [1, 8, 3, 0, 2, 0, 1, 10, 13, 0]
Output: [1, 8, 3, 2, 1, 10, 13, 0, 0, 0]

Input:  [0, 3, 5, 9, 0, 0, 23, 2]
Output: [3, 5, 9, 23, 2, 0, 0, 0]

Brute force: build a second array

Copy the non-zero elements into a new array. A new int[] starts filled with zeros, so the padding is already there. Then copy it back.

Java

import java.util.Arrays;

public class Main {
    static void moveZeroes(int[] nums) {
        int[] result = new int[nums.length]; // all zeros
        int k = 0;
        for (int x : nums) {
            if (x != 0) {
                result[k++] = x;
            }
        }
        System.arraycopy(result, 0, nums, 0, nums.length);
    }

    public static void main(String[] args) {
        int[] a = {1, 8, 3, 0, 2, 0, 1, 10, 13, 0};
        moveZeroes(a);
        System.out.println(Arrays.toString(a));
    }
}

Output

[1, 8, 3, 2, 1, 10, 13, 0, 0, 0]

Time: O(n). Space: O(n).

Optimal: in-place write pointer

Keep write, the position where the next non-zero element belongs. Scan the array, and swap each non-zero element into position write. Everything before write is non-zero and in the original order, and everything between write and the scan position is zero.

Java

import java.util.Arrays;

public class Main {
    static 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++;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 8, 3, 0, 2, 0, 1, 10, 13, 0};
        moveZeroes(a);
        System.out.println(Arrays.toString(a));

        int[] b = {0, 3, 5, 9, 0, 0, 23, 2};
        moveZeroes(b);
        System.out.println(Arrays.toString(b));
    }
}

Output

[1, 8, 3, 2, 1, 10, 13, 0, 0, 0]
[3, 5, 9, 23, 2, 0, 0, 0]

Time: O(n). Space: O(1).

Before the first zero, write == read, and the swap does nothing. Afterwards, nums[write] is always a zero, so each swap moves exactly one zero one step further back.

Edge cases

No zeros or only zeros: the array does not change.
An Integer[] or List<Integer>: sorting with Comparator.comparing(x -> x == 0) gives the same result, because the object sort is stable and false sorts before true. It takes O(n log n) time. (Arrays.sort on a primitive int[] takes no comparator.)