Algorithm
- Take array as input from the user-
- Declare two pointers viz. Check pointer and Assign pointer and initialize them to the rightmost index of the array.
-
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.
- Keep repeating step 3 until the Check pointer reaches the lowest index of the array.
- 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).
Also see, Rabin Karp Algorithm
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].
Conclusion
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.
Recommended Readings:
Recommended problems -
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 Coding Ninjas Studio.
305+ registered