How do you move all the zeros to the left of the array?

How do you move all the zeros to the left of the array?
How do you move all the zeros to the left of the array?

Introduction

Let’s say you have an array of integers and have to move all the zeros to the left of the array. You have to do this without changing the original order of non-zero numbers in the array. Let’s understand this with the following example. 

Example

The solution using two pointers

The basic idea used to move the zeros to the left of the array is that we take two-pointers viz. Check pointer and Assign pointer. We start with initializing both of them to the last index of the array, and we then begin with moving the Check pointer to the left. If we find an index storing zero, we check the next index without doing anything.

In contrast, if we encounter an index with a value other than zero, we store that value at the index pointed by the Assign pointer, then decrease its value one. We keep traversing the array like this until the Check pointer reaches the leftmost index of the array. Once it reaches the left-most index of the array, we start moving the Assign pointer to the left end by filling all the indexes with 0.


We can understand the above example with the image given below-

The red arrow is the Check pointer, and the blue arrow is the Assign pointer. The Check pointer keeps moving one index leftwards at a time, but the Assign pointer moves only if the Check pointer encounters a non-zero number. And, in the final step, when the Check pointer reaches the left end of the array, we move the Assign pointer to the left while assigning zero to all the indexes.

The solution using two pointers

Algorithm

  1. Take array as input from the user-
  2. Declare two pointers viz. Check pointer and Assign pointer and initialize them to the rightmost index of the array.
  3. Start with checking the value at the index pointed by the Check pointer-
  • If it is 0, decrease its index by one and repeat the process
  • If it is a non-zero number, assign the value it holds to the index pointed by the Assign pointer and decrease its index by 1.
  1. Keep repeating step 3 until the Check pointer reaches the lowest index of the array.
  2. Once the Check pointer reaches the lowest index of the array, move the Assign pointer to the lowest index by assigning zero to the index it passes through.

Implementation of the solution(C++)

#include <bits/stdc++.h>
using namespace std;
//Function to move the zeros to the left. It takes
//the vector and its size as arguments.
void MovezerosToTheLeft(vector<int> &numbers, int n)
{
    if(n<1)
    { 
        return;
    }
    //Declare and initialize both the pointers.
    int checkptr=n-1;
    int assignptr=n-1;
    //While loop for moving the check pointer
    //towards left untill it reaches left most 
    //index. 
    while(checkptr>=0)
    {
        //To move the assign pointer after changing
        //the value, if the numbers[checkptr] is
        //not equal to 0.
        if(numbers[checkptr]!=0)
        {
            numbers[assignptr]=numbers[checkptr];
            assignptr--;
        }
        checkptr--;
    }
    //To fill rest of left indexes with 0.
    while(assignptr>=0)
    {
        numbers[assignptr]=0;
        assignptr--;
    }
}
//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.
    MovezerosToTheLeft(numbers,n);
    //Printing the vector.
    for(int i=0;i<n;i++)
    {
        cout<<numbers[i]<<" ";
    }
    return 0;
}

Input:

9
1 2 3 0 0 0 0 0 0

Output:

Enter the number of elements in the array.
Enter array elements-
0 0 0 0 0 0 1 2 3

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

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

Frequently asked questions

How do you move all zeros to the left of the array?

We can move all zeros to the left of the array using a two-pointer approach as the one discussed in this article.

How do you separate zeros from non-zeros in an array?

We can separate all the zeros to the left of the array, or the right of the array, using the two pointer approach.

How do you remove zeros from an array?

It can be easily done by any of these two methods- separating the zeroes in the array and then removing the array or directly removing them. A simpler method could adopt the approach similar to the method discussed above to move all the zeros to the left of the array, with the modification that whenever the Check pointer encounters a zero, the zero gets deleted from the array.

How do I remove a specific element from an array?

We traverse the whole array, and whenever we find that element, we delete it. This way, we can remove a specific element from an array.

How do I remove one element from an array?

You can use that by searching the array to find the location of that element, then delete the value at that index in the array by accessing it with array [index].

Key takeaways

In this blog, we discussed how we could move all the zeros to the left of the array that only contains integers-

We did it by taking two-pointers and then initializing them to the last index of the array, then started moving the first pointer towards the left. If we encountered zero, we would continue to the next index. But if we met any non-zero number, we put that number at the index pointed by the second pointer.

Once the first point finishes traversing the array, we take the index pointed by the second array and fill zeros in all the indexes on the left of it.

You can read more about two-pointer approaches to solve programming questions and practice similar problems on CodeStudio.

If you liked this blog, share it with your friends.

Exit mobile version