Problem: Given an array of numbers, move all zeros to the right while maintaining the relative ordering of the non-zero items. For example, given [0, 8, 0, 15, 4], modify the array to [8, 15, 4, 0, 0].

Constraints:

• The length of the array is between 1 and 10^4.
• A number is between -2^31 and 2^31 - 1.

Initial thought process (Brute-force)

First, we note that the question requires us to modify the existing array, rather than returning a new array. We need to always clarify the requirements before diving into the solutions. Having this in mind, we start with a brute-force solution of copying non-zero element to another array and copying everything back to the original array.

An intuition here is that moving all zeros to the right is logically equivalent to moving all non-zeros to the left. We can move all non-zeros to the left while iterating through an array once and copying over non-zeros to a temporary array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public void moveZeros(int[] nums) {
        int[] tmp = new int[nums.length];
        int tmpCursor = 0;

        // Move non-zeros to the temporary while preserving the order
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                tmp[tmpCursor] = nums[i];
                tmpCursor++;
            }
        }

        // Copy the temporary array back to the original array
        for (int i = 0; i < nums.length; i++) {
            nums[i] = tmp[i];
        }
    }
}

Let’s define N as the length of the input array. Then, the time complexity of the brute-force solution is O(N) because the solution iterates through the elements. The space complexity is also O(N) because the solution allocates a temporary array whose length is equal to the input array.

Inefficient in-place solution

The time complexity cannot be better than O(N) in that it is necessary to examine all elements of the array to move all zeros to the right. On the other hand, space complexity could be improved if we can somehow avoid allocating a temporary array. During an interview setting, a follow-up question could be to improve the space complexity by implementing an in-place solution.

We can implement an in-place solution by literally doing what the question requires–that is, by going through each elements in the input array from left to right, and keep moving a zero to the right.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public void moveZeros(int[] nums) {
        // Go through each elements in the array.
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                int k = i;

                // If the element is zero, keep swapping with
                // all non-zero elements to the right.
                for (int j = k + 1; j < nums.length; j++) {
                    if (nums[j] != 0) {
                        swap(nums, k++, j);
                    }
                }
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Let us walk through the solution using an input [0, 8, 0, 15, 4].

// beginning
[0, 8, 0, 15, 4]

// At the end of iteration 1, nums[0] would be moved to the position '^' below.
[8, 0, 15, 4, 0]
 i            ^

// At the end of iteration 2, nums[1] would be moved to the position '^' below.
[8, 15, 4, 0, 0]
    i      ^

// iteration 3 is a noop.
[8, 15, 4, 0, 0]
        i

// iteration 4 is a noop.
[8, 15, 4, 0, 0]
           i

// iteration 5 is a noop.
[8, 15, 4, 0, 0]
              i

The space complexity of this solution is constant because we no longer allocate a temporary array. On the other hand, the time complexity is O(N^2) where N is the length of the input array. The reason is that we have an outer loop that iterates through all elements in an array, and in the worst case, the inner loop iterates through the rest of the array. For example, given [0, 0, 0, 0, 0], the inner loop will touch 4, 3, 2, and 1 element for each iteration of the outer loop.

Optimized in-place solution

The naive implementation is not ideal as it has a quadratic time complexity. Can we do better? We can implement an in-place solution with a linear time complexity based on two intuitions:

1. We don’t need to actually keep swapping the elements to maintain relative ordering.
2. Moving all zeros to the right is equivalent to moving all non-zeros to the left.

The first intuition is the key to the optimization. To explain, let us partition the input array into two parts. Define an index i such that:

• (invariant 1) All elements nums[0], …, nums[i - 1] are non-zeros and are in the relative order in which they originally appeared in the input.
• All elements nums[i - 1], …, nums[nums.length - 1] can be either zero or non-zeros (i.e. not yet processed).

If we iterate through the array, and keep copying all non-zeros to the left (intuition 2) while maintaining the first invariant, we will not need to keep swapping a zero with elements to its right.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public void moveZeros(int[] nums) {
        // Invariant: nums[0], ..., nums[i - 1] are non-zero
        // and are in the relative order that they originally appeared.
        int i = 0;

        // Iterate through the array, and copy non-zeros to the first partition
        // of the array and expand the partition.
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != 0) {
                nums[i] = nums[j];
                i++;
            }
        }

        // All non-zeros have been copied to the first partition.
        // Fill the second partition with zeros.
        for (int j = i; j < nums.length; j++) {
            nums[j] = 0;
        }
    }
}

Complexity

Let N be the length of the input array. The time complexity is O(N) because we iterate through the array constant times. The space complexity is O(1) because we do not require any additional space and modify the array in-place.

Validation

Both in an interview setting and in the real life, we should validate the input according to the constraints. Additionally, we should clarify the constraints before diving into a solution.

Let’s validate the length of the input array. Here, we will throw an exception if the validation fails. In an interview setting, we will need to clarify and agree with the interviewer on the behavior in case of an invalid input.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public void moveZeros(int[] nums) {
        // Validate the input
        int n = nums.length;
        if (n < 1 || n > 10e4) {
            throw new IllegalArgumentException(
                String.format(
                    "The input array must be between 1 and 10^4 in length. " +
                    "But the length was %d.", n
                )
            );
        }

        // ...
    }
}

We will not validate that each number in the array lies between -2^31 and 2^31 - 1, because int type in Java is already between that range. However, depending on the programming language, you might need to explicitly validate this constraint.

Lessons learned

1. Start with a brute-force approach and find opportunities to optimize the solution.
2. If you find yourself modifying an array in a nested loop, try to maintain two pointers and modify the array while maintaining an invariant.
3. If you find yourself keep moving elements over and over, Partition an array and think in terms of an invariant. (This is similar to lesson learned #1 in Minimum Swaps to Make Strings Equal)
4. Turning the requirement on its head could simplify the solution. For instance, we were able to simplify the solution by moving non-zeros to the left, rather than moving zeros to the right.