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, 6, 0, 2, 0, 1, 15, 12, 0]

Output: X[] = [4, 8, 6, 2, 1, 15, 12, 0, 0, 0]

Example 2

Input: X[] = [0, 3, 5, 9, 0, 0, 23, 2]

Output: X[] = [3, 5, 9, 23, 2, 0, 0, 0]

Follow-up questions for the interviewer

• Candidate: Do we need to maintain the relative order of elements in 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, it 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 would be to take extra memory of size n and traverse the input array to store all the non-zero elements at the starting indexes of the additional memory. After this, we 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, i.e. we are using extra space to generate the output. 2) We use two loops to store the output in extra space.

Solution steps

• We declare an extra memory output[n].
• We initialize two-loop pointers: Pointer i for traversing the input array and pointer j for storing values in the output array.
• 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 pointer i. 
• By the end of 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.

Solution pseudocode

int[] moveZeroesEnd(int X[], int n)
{
    int output[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: List[int]) -> List[int]:
    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). In other words, we are doing a single traversal of both arrays in the worst case. Think!

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 can use the idea of above approach, but rather than storing output in extra space, we shift the non-zero elements at the start of the input array itself and fill the remaining part with the zeroes. Here are the steps:

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

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

Solution pseudocode

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, then 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 at X[i] is non-zero, instead of updating X[j] with X[i], if we swap the element at index i with index j, then we wouldn’t need to fill the rest of the array with zeroes at the end. All non-zero elements will be moved to the end due to swapping. Think!

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

Solution pseudocode

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

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;
        }
    }
}

Solution analysis

We are doing only a single traversal where comparison and swapping are critical operations. Time complexity = O(n), Space complexity = O(1).

Important Note: We recommend learners transform the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verify all the test cases. Please let us know if you find any errors or bugs; we would be highly grateful. Enjoy programming!

Critical ideas to think!

• Using a similar approach, can we sort an array with only two values repeated? 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 some other approach? Can we use two pointers moving in the opposite direction?
• Will the above approaches preserve relative order of non-zero elements?
• Explain the best and worst-case scenarios of all three approaches.
• In the 2nd approach, why are we traversing again to store zeroes to the end of input array?

Comparisons of time and space complexities

• Brute force approach : Time = O(n), Space = O(n)
• Two pointers(Two loops): Time = O(n), Space = O(1)
• Two pointers(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
• Move all values equal to K to the end of the Array
• The minimum swaps required to sort the array in ascending order

Enjoy learning, Enjoy coding, Enjoy algorithms!