Move all the zeros to the end of the given array

0
194
Move all the zeros to the end of the given array

In the given array move all the zeros in the array to the end of the array.

Example

Input : [9,17,0,14,0,0,23,19,4]
Output : [9,17,4,14,19,23,0,0,0]

Algorithm

Time Complexity: O(n), n is size of array.
Space Complexity:O(1)

Step 1 : In the given array, take two pointers like variables. Initialize left = 0, right = N -1 (N is size of the array).
a.    Left is left pointer variable at the first element.
b.    Right is right pointer variable at the last element.

Step 2 : Traverse from left such that if a zero is found toward start and non-zero towards end then simply swap them.
a.    From left, if element is non-zero move ahead.
b.    If zero is found then, traverse from back towards non-zero elements from the right pointer, if zero found continue traversing.
c.    If non-zero found, swap with the left pointer.
d.    Finally all the zeros are pushed to the end of the array.

Step 3 : Print the array after traversing to check the zeroes are pushed to the end.

Algorithm working Example

Therefore,
For the given input : [9,17,0,14,0,0,23,19,4]
Output : [9,17,4,14,19,23,0,0,0]

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	
	int arr[] = {9,24,0,16,39,1,0,0,7,6,0,4,3,49,0,50,36};// array
	int N = sizeof(arr)/sizeof(arr[0]); //sizeofarray
	
	int left = 0 , right = N-1; // take two pointer like variables for traversal
	
	while(left < right)
	{
		if(arr[left] != 0) // if element not zero then move ahead
			left ++;
		if(arr[right] == 0) // if ending elments are zero then come backwards towards non zero elements
			right --;
			
		if(arr[left] == 0 and arr[right] != 0) // if a zero is found towards start and non zero towards end then simply swap it
				{	
				swap(arr[left++],arr[right--]);
				}
	} 
	
	for(int i = 0; i < N;i++)
		cout <<arr[i]<<" ";
	return 0;
}

Try It

LEAVE A REPLY

Please enter your comment!
Please enter your name here