# 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 PointersViews 2003

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

### 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

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

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

References

Translate »