Move all Zeroes to End of Array

Difficulty: Easy, Asked-in: Facebook, Amazon, Uber, LinkedIn, Bloomberg.

Key-takeaway: An excellent problem to learn problem-solving using single loop and two pointers approach. In two-pointers approach, both pointers are moving in the same direction.

Let’s understand the problem

Given an array X[] of n integers, where some elements are zero and some elements are non-zero. Write a program to move all the zeroes to the end of the array.

Example 1

Input: X[] = [4, 8, 0, 0, 2, 0, 1, 0], Output: X[] = [4, 8, 2, 1, 0, 0, 0, 0]

Explanation: The zeros are moved to the end of the array while maintaining the order of non-zero elements.

Example 2

Input: X[] = [1, 2, 3, 4, 0, 0, 0], Output: [1, 2, 3, 4, 0, 0, 0]

Explanation: Since the zeros are already at the end of the array, the array remains unchanged.

Example 3

Input: X[] = [0, 0, 1, 2, 0, 3, 4], Output: [1, 2, 3, 4, 0, 0, 0]

Follow-up questions for the interviewer

• Candidate: Do we need to maintain the relative order of elements in the output? Interviewer: Yes, we need to preserve the relative order of non-zero elements.
• Candidate: Do we need to solve this problem in-place? Interviewer: Yes, we are looking for an O(n) in-place solution.
• Candidate: Other than zero, are input values unique? Interviewer: No, they can be repeated.

Discussed solution approaches

• Brute force approach  using extra space and two single loops
• Two pointers in-place solution using two single loops
• Two pointers in-place solution using a single loop

Brute force approach  using extra space and two single loops

Solution idea

One basic idea is to allocate extra memory of size n and traverse the input array to store all the non-zero elements at the starting indexes of the extra memory. After this, we can fill the remaining extra memory space with zeroes.

This solution will preserve the order of elements, but there are two drawbacks:

1. This is not an in-place solution because we are using extra space to generate the output.
2. We require two loops to store the output in the extra space.

Solution steps

1. We declare extra memory output[n].
2. We initialize two pointers for the loop: i for traversing the input array and j for storing values in the output array.
3. Now we run a loop from i = 0 to n - 1 and traverse the input array. When we find a non-zero element X[i], we store it at output[j] and increment both i and j. Otherwise, we increment the i pointer.
4. By the end of the loop, output[] stores all the non-zero elements from index 0 to j - 1. So, we traverse output[] until j < n and store zeroes at the remaining end. After this, we return the output[] array.

Implementation code C++

int* moveZeroesEnd(int X[], int n)
{
    int* output = new int[n];
    int j = 0;
    for (int i = 0; i < n; i = i + 1)
    {
        if (X[i] != 0)
        {
            output[j] = X[i];
            j = j + 1;
        }
    }
    while (j < n)
    {
        output[j] = 0;
        j = j + 1;
    }
    return output;
}

Implementation code Python

def moveZeroesEnd(X):
    n = len(X)
    output = [0] * n
    j = 0
    for i, x in enumerate(X):
        if x != 0:
            output[j] = x
            j = j + 1
    return output

Solution analysis

Time complexity in the worst case = Time complexity of traversing X[] and storing non-zero elements in output[] + Time complexity of storing zeroes in output[] = O(n) + O(n) = O(n).

The worst-case scenario occurs when all array elements are zero (traversal of both arrays) and the best-case scenario occurs when all array elements are non-zero (Single traversal of input array).

Space complexity = O(n), for extra space output[].

Two pointers in-place solution using two single loops

Solution idea and steps

The critical question is: Can we further optimize the space complexity of the above solution and solve the problem in place? Let's think!

We will use an idea similar to the above approach, but instead of storing the output in extra space, we will shift the non-zero elements to the start of the input array itself and fill the remaining part with zeroes.

Here are the steps:

1. We traverse the input array using two pointers, i and j, where i is for traversing the array and j is for tracking the last index of the non-zero element.
2. Whenever we encounter a non-zero element at index i, we shift it to index j, i.e., if X[i] != 0, then X[j] = X[i]. We also increment both i and j by 1.
3. Otherwise, if we encounter a zero, we ignore it and move the pointer i by 1.
4. By the end of the loop, all elements in X[0...j - 1] are non-zero elements. Then, we traverse X from index j to n - 1 and fill it with zeroes.

This solution will preserve the order of elements, but there is one drawback: we are using two loops to generate the output.

Implementation code C++

void moveZeroEnd(int X[], int n)
{
    int j = 0;
    for (int i = 0; i < n; i = i + 1)
    {
        if (X[i] != 0)
        {
            X[j] = X[i];
            j = j + 1;
        }
    }
    while (j < n)
    {
        X[j] = 0;
        j = j + 1;
    }
}

Implementation code Python

def moveZeroesEnd(X, n):
    j = 0
    for i in range(n):
        if X[i] != 0:
            X[j] = X[i]
            j = j + 1
    while j < len(X):
        X[j] = 0
        j = j + 1 

Solution analysis

Time complexity in the worst case = Time complexity of traversing X[] to shift non-zero elements + Time complexity of traversing X[] to fill zeroes = O(n) + O(n) = O(n). We are solving the problem in-place, so space complexity = O(1).

Two pointers in-place solution using single loop

Solution idea

Can we further optimize the above approach and solve it using a single loop? Can we reduce the second traversal to fill the zero at the end? Let's think!

If we observe the intermediate step of the first loop in the above solution, we can observe a pattern:

• All the elements from 0 to j - 1 are non-zero.
• All the elements from j to i - 1 are zero.
• All the elements from i to n - 1 still need to be explored.

So, when the element X[i] is non-zero, instead of updating X[j] with X[i], if we swap the element at index i with the element at index j (first zero elements), then we wouldn't need to fill the rest of the array with zeroes at the end. All zero elements will be moved to the end due automatically to the swapping. Think!

Note: This solution idea is similar to the partition process of the quick sort.

Implementation code C++

void moveZeroEnd(int X[], int n)
{
    int j = 0;
    for (int i = 0; i < n; i = i + 1)
    {
        if (X[i] != 0)
        {
            swap(X[j], X[i]);
            j = j + 1;
        }
    }
}

Implementation code Python

def moveZeroEnd(X, n):
    j = 0
    for i in range(n):
        if X[i] != 0:
            X[i], X[j] = X[j], X[i]
            j = j + 1

Optimized version of the above code

In the above code, if some non-zero elements are continuously present at the starting indexes, unnecessary swapping will occurs. So, how can we optimize the above code?

Here's an idea: Inside the loop, when X[i] is non-zero, we can check if i and j are not the same. If they are same, we do nothing and move forward. If they are different, we directly assign the non-zero element at index i to X[j] and assign 0 to X[i]. This approach will eliminate unnecessary swapping.

void moveZeroEnd(int X[], int n)
{
    int j = 0;
    for (int i = 0; i < n; i = i + 1)
    {
        if (X[i] != 0)
        {
            if (i != j)
            {
                X[j] = X[i];
                X[i] = 0;
            }
            j = j + 1;
        }
    }
}

Solution analysis

We are doing a single traversal where comparison is the critical operation. Time complexity = O(n), Space complexity = O(1).

Critical ideas to think!

• Can we sort an array with only two repeated values using a similar approach? How will we solve this when three values are repeated?
• In the efficient approach, what would be the count of swap operations in the worst-case scenario?
• Can we solve this problem using a different approach? Can we use two pointers moving in the opposite direction?
• Will the above approaches preserve the relative order of non-zero elements?
• Explain the best and worst-case scenarios for all three approaches.
• In the second approach, why are we traversing again to store zeroes at the end of the input array?

Comparisons of time and space complexities

• Brute force approach : Time = O(n), Space = O(n).
• Two pointers(Two single loops): Time = O(n), Space = O(1).
• Two pointers(One single loop): Time = O(n), Space = O(1).

Suggested coding questions to practice

• Double the first element and move zero to the end
• Segregate even and odd numbers
• Segregate 0s and 1s in an array
• Sort an array of 0s, 1s, and 2s in linear time and constant space.
• Move all values equal to K to the end of the Array
• Find minimum swaps required to sort the array in ascending order
• Move all negative numbers to the beginning of the array.
• Move all duplicates to the end of the array while keeping the unique elements in their original order.
• Separate an array of characters such that all uppercase letters come before lowercase letters.
• Partition an array of integers into three parts: elements less than a given value, elements equal to the value, and elements greater than the value.

Enjoy learning, Enjoy coding, Enjoy algorithms!