Home » Technical Interview Questions » Array Interview Questions » Move All the Zeros to the End of the Given Array

Move All the Zeros to the End of the Given Array


Reading Time - 5 mins

In the given array move all the zeros which are present in the array to the end of the array. Here there is always a way exist to insert all the number of zeroes to the end of the array.

Example

Input

9

9 17 0 14 0 0 23 19 4

Output

9 17 4 14 19 23 0 0 0

Algorithm for Move All the Zeros to the End of the Given Array

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 the left pointer variable at the first element.
b.    Right is the right pointer variable at the last element.

Step 2: Traverse from left such that if a zero is found toward the start and non-zero towards the end then simply swap them.
a.    From left, if the element is non-zero move ahead.
b.    If zero is found then, traverse from the 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.

Explanation for Move All the Zeros to the End of the Given Array

a[] = {9, 17, 0, 14, 0, 0, 23, 19, 4}

READ  Queries for counts of array elements with values in given range

1st Step: Left at 0 and Right at n-1.

2nd Step: Increment the left pointer till we encounter 0. Then left=2. Now we swap a[left], a[right], and increment the left pointer and reduce the right pointer which denotes the non zero elements in the array.

 3rd Step: Next we increment left pointer till we encounter another zero, Then left=4. Now we swap a[left], a[right], and increment the left pointer and reduce the right pointer which denotes the non zero elements in the array.

4th Step: Here we already encounter a zero. So, we swap it with the element present at the right pointer position.

5th Step: Now, increment left pointer till we encounter any zero. Now we keep increment and our left>right so we terminate the loop.

Therefore, For the given input [9,17,0,14,0,0,23,19,4] our output is [9,17,4,14,19,23,0,0,0].

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  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;
}
9
9 17 0 14 0 0 23 19 4
9 17 4 14 19 23 0 0 0
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions