Move All the Zeros to the End of the Given Array

Problem Statement

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}

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].

Implementation

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;
}

import static java.lang.Math.sqrt;
import java.util.Arrays;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        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 && arr[right] != 0) // if a zero is found towards start and non zero towards end then simply swap it
              {  
              arr[left]=arr[left]+arr[right]-(arr[right]=arr[left]);
              left++;
              right--;
              }
        } 

        for(int i=0;i<n;i++)
          System.out.print(arr[i]+" ");
    }
}

9
9 17 0 14 0 0 23 19 4

9 17 4 14 19 23 0 0 0