Move All the Zeros to the End of the Given Array  

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Capital One Cisco Dell eBay Facebook Goldman Sachs Google IBM LinkedIn Microsoft Nutanix Oracle PayPal Paytm Qualcomm Samsung SAP Labs ServiceNow Splunk Tesla Uber Walmart Labs Yahoo Yandex Zillow
Array Two Pointers

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

Please click Like if you loved this article?

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.

See also
Shuffle 2n integers as a1-b1-a2-b2-a3-b3-..bn without using extra space

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

Java Program

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

Complexity Analysis for Move All the Zeros to the End of the Given Array  

Time Complexity

See also
Merge Two Balanced Binary Search Trees

O(n) where n is the size of the array. Here we just use two-pointer and keep reducing the length between them. So, it leads us to linear time complexity.

Space Complexity

Please click Like if you loved this article?

O(1) because here we use only a few variables which leads us to constant space complexity.

References

Please click Like if you loved this article?