How Do You Move All The Zeros To The End Of The Array?

Introduction

Suppose you are given an array containing integers and asked to move all the zeros to the end of the array. While doing that, you have to ensure that the non-zero numbers in the array appear in the same order in which they appeared in the original array. Let’s start with understanding the problem with an example.

There could be many ways to solve this problem, but we will discuss one of the most common and simple methods: two use a count variable to keep track of the number of nonzeros in the array. Let’s understand this method in detail-

The Solution using a Count Variable

The logic behind this method to move the zeros to the end of the array is to traverse the array from the left end and maintain the count of non-zero numbers. While traversing the array, whenever we encounter a non-zero number, we place it at the Array[count] and increase the count value by one. Once we complete traversing the array, we fill the zeros from the Array[count] to the last index of the array.

To help you understand this method, let’s see an example where we use the above method to move zeros to the end of the array- 

In this example, we have used the red arrow to indicate the variable used to traverse the array from left to right, and we also see the value of the count variable in each step. We start with both values as 0; the red pointer keeps moving one index in the right direction in each step until it reaches the end. Meanwhile, if it encounters a non-zero number at any index, it inserts that number at Array[count] and increases the count variable by 1.

Finally, when the red pointer reaches the end, we start moving the count until it is equal to the last index of the array and assign zero to all the indexes it moves through.

Algorithm

1. Take an array as input from the user.
2. Declare a count variable with a value equal to 0.
3. Start traversing the array using a loop, check the number at each index as per the following conditions-

• If it is 0, continue traversal without doing any operation. 
• If it is a non-zero number, assign the value it holds to the Array[count] and increase its value by 1.

4. Keep repeating step 3 until the traversal of the array is complete.
5. Once we complete the traversal, increase the count variable until the last index and assign 0 to the indexes, it passes through.

Implementation of the Solution

#include <bits/stdc++.h>
using namespace std;
//Function to move the zeros to the end of the array. It takes
//the v5ector and its size as arguments.
void MovezerosToTheEnd(vector<int> &numbers, int n)
{
    //Declare and initialize both count the variable.
    int count=0;
    //Using for loop to iterate the array.
    for(int i=0;i<n;i++)
    {
        //If the value at a index is 0, continue traversal and 
        //in case of non-zero elements put them at the index 
        //'count' and increase the value of count by one. 
        if(numbers[i]!=0)
        {
            numbers[count++]=numbers[i];
        }
    }
    //To fill rest of indexes with 0.
    while(count<n)
    {
        numbers[count++]=0;
    }
}
//Driver function.
int main()
{
    int n;
    cout<<"Enter the number of elements in the array."<<endl;
    cin>>n;
    vector<int> numbers;
    cout<<"Enter array elements-"<<endl;
    //Taking input in the vector.
    for(int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        numbers.push_back(a);
    }
    //Function call.
    MovezerosToTheEnd(numbers,n);
    //Printing the vector.
    for(int i=0;i<n;i++)
    {
        cout<<numbers[i]<<" ";
    }
    return 0;
}

Input-

9
0 0 0 0 5 6 8 0 1

Output-

Enter the number of elements in the array.
Enter array elements-
5 6 8 1 0 0 0 0 0

The time complexity of this algorithm is O(N).

The space complexity of this algorithm is O(1).

We can also implement this approach using a swap function where we iterate from the beginning of array and swap every non-zero element encountered with the element present at index ‘count’ which ensures the non zero elements are placed in the same order as they appear in the original array ,here count denotes the number of non-zero elements found so far.

Hence, rewriting the MovezerosToTheEnd function in the above code as-

void MovezerosToTheEnd(vector<int> &numbers, int n)
{
    //Declare and initialize both count the variable.
    int count=0;
    //Using for loop to iterate the array.
    for(int i=0;i<n;i++)
    {
        //If the value at a index is 0, continue traversal and 
        //in case of non-zero elements put swap it with the number at
        //number[count++]. 
        if(numbers[i]!=0)
        {
            swap(numbers[count++], numbers[i]);
        }
    }
}

Frequently Asked Questions

Key Takeaways

In this blog, we talked about the solution to the problem, asking to move all the zeros to the end of the array, given that it only contains integers and we have to keep the non-zeros numbers in the order they appear in the original array-

We solved this problem using a count variable; we declared the count variable with the value 0. Then we started traversing the array. If we encountered a 0, we continued to traverse the array, and if we met a non-zero number, we put it to the ‘count’ index of the array. And increase the value of the count by 1. We keep doing this until we complete traversing the array. Then we will start increasing the count variable until its value is equal to the last index of the array, and we keep filling all the indexes it traverses with zeros.

Visit here to learn more about arrays. You can also practice similar problems on CodeStudio. If you liked this blog, share it with your friends.

By: Gorakhnath Yadav