# Move all Zeros to the end of the array

In this article we will learn how to solve the most asked coding interview problem: “Move all Zeros to the end of the array”

Problem Statement: You are given an array of integers, your task is to move all the zeros in the array to the end of the array and move non-negative integers to the front by maintaining their order.

Examples
```Example 1:
Input: 1 ,0 ,2 ,3 ,0 ,4 ,0 ,1
Output: 1 ,2 ,3 ,4 ,1 ,0 ,0 ,0
Explanation: All the zeros are moved to the end and non-negative integers are moved to front by maintaining order

Example 2:
Input: 1,2,0,1,0,4,0
Output: 1,2,1,4,0,0,0
Explanation: All the zeros are moved to the end and non-negative integers are moved to front by maintaining order```

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Brute Force Approach Optimal Approach
Brute Force Approach
Algorithm / Intuition

### Brute Force Approach:

The extremely naive solution, we can think of, involves the use of an extra array. The algorithm is as follows.

### Algorithm:

• Suppose, there are N-X zeros and X non-zero elements in the array. We will first copy those X non-zero elements from the original array to a temporary array.
• Then, we will copy the elements from the temporary array one by one and fill the first X places of the original array.
• The last N-X places of the original array will be then filled with zero. Now, our task is completed.

Dry run: Please refer video for it.

Code
``````

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

vector<int> moveZeros(int n, vector<int> a) {
//temporary array:
vector<int> temp;
//copy non-zero elements
//from original -> temp array:
for (int i = 0; i < n; i++) {
if (a[i] != 0)
temp.push_back(a[i]);
}

// number of non-zero elements.
int nz = temp.size();

//copy elements from temp
//fill first nz fields of
//original array:
for (int i = 0; i < nz; i++) {
a[i] = temp[i];
}

//fill rest of the cells with 0:
for (int i = nz; i < n; i++) {
a[i] = 0;
}
return a;
}

int main()
{
vector<int> arr = {1, 0, 2, 3, 2, 0, 0, 4, 5, 1};
int n = 10;
vector<int> ans = moveZeros(n, arr);
for (auto &it : ans) {
cout << it << " ";
}
cout << '\n';
return 0;
}

```
```
``````

import java.util.*;

public class tUf {
public static int[] moveZeros(int n, int []a) {
//temporary array:
ArrayList<Integer> temp = new ArrayList<>();
//copy non-zero elements
//from original -> temp array:
for (int i = 0; i < n; i++) {
if (a[i] != 0)
}

// number of non-zero elements.
int nz = temp.size();

//copy elements from temp
//fill first nz fields of
//original array:
for (int i = 0; i < nz; i++) {
a[i] = temp.get(i);
}

//fill rest of the cells with 0:
for (int i = nz; i < n; i++) {
a[i] = 0;
}
return a;
}

public static void main(String[] args) {
int[] arr = {1, 0, 2, 3, 2, 0, 0, 4, 5, 1};
int n = 10;
int[] ans = moveZeros(n, arr);
for (int i = 0; i < n; i++) {
System.out.print(ans[i] + " ");
}
System.out.println("");
}
}
```
```
``````

def moveZeros(n: int,  a: [int]) -> [int]:
# Temporary array
temp = []

# Copy non-zero elements from original to temp array
for i in range(n):
if a[i] != 0:
temp.append(a[i])

# Number of non-zero elements
nz = len(temp)

# Copy elements from temp to fill first nz fields of original array
for i in range(nz):
a[i] = temp[i]

# Fill the rest of the cells with 0
for i in range(nz, n):
a[i] = 0

return a

arr = [1, 0, 2, 3, 2, 0, 0, 4, 5, 1]
n = 10
ans = moveZeros(n, arr)
for it in ans:
print(it, end=" ")
print()

```
```
``````

function moveZeros(n, a) {
// Temporary array
let temp = [];

// Copy non-zero elements from original array to temp array
for (let i = 0; i < n; i++) {
if (a[i] !== 0) {
temp.push(a[i]);
}
}

// Number of non-zero elements
let nz = temp.length;

// Copy elements from temp and fill the first nz fields of the original array
for (let i = 0; i < nz; i++) {
a[i] = temp[i];
}

// Fill the rest of the cells with 0
for (let i = nz; i < n; i++) {
a[i] = 0;
}

return a;
}

let arr = [1, 0, 2, 3, 2, 0, 0, 4, 5, 1];
let n = 10;
let ans = moveZeros(n, arr);
console.log(ans.join(' '));

```
```

Output: 1 2 3 2 4 5 1 0 0 0

Complexity Analysis

Time Complexity: O(N) + O(X) + O(N-X) ~ O(2*N), where N = total no. of elements,
X = no. of non-zero elements, and N-X = total no. of zeros.
Reason: O(N) for copying non-zero elements from the original to the temporary array. O(X) for again copying it back from the temporary to the original array. O(N-X) for filling zeros in the original array. So, the total time complexity will be O(2*N).

Space Complexity: O(N), as we are using a temporary array to solve this problem and the maximum size of the array can be N in the worst case.
Reason: The temporary array stores the non-zero elements. In the worst case, all the given array elements will be non-zero.

Optimal Approach
Algorithm / Intuition

### Optimal Approach(Using 2 pointers):

We can optimize the approach using 2 pointers i.e. i and j. The pointer j will point to the first 0 in the array and i will point to the next index.

Assume, the given array is {1, 0, 2, 3, 2, 0, 0, 4, 5, 1}. Now, initially, we will place the 2-pointers like the following:

The algorithm will be the following.

### Algorithm:

1. First, using a loop, we will place the pointer j. If we don’t find any 0, we will not perform the following steps.
2. After that, we will point i to index j+1 and start moving the pointer using a loop.
3. While moving the pointer i, we will do the following:
1. If a[i] != 0 i.e. a[i] is a non-zero element: We will swap a[i] and a[j]. Now, the current j is pointing to the non-zero element a[i]. So, we will shift the pointer j by 1 so that it can again point to the first zero.
4. Finally, our array will be set in the right manner.

Dry run: Please refer video for a detailed dry run.

The first 2 steps are shown below:

Code
``````

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

vector<int> moveZeros(int n, vector<int> a) {
int j = -1;
//place the pointer j:
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
j = i;
break;
}
}

//no non-zero elements:
if (j == -1) return a;

//Move the pointers i and j
//and swap accordingly:
for (int i = j + 1; i < n; i++) {
if (a[i] != 0) {
swap(a[i], a[j]);
j++;
}
}
return a;
}

int main()
{
vector<int> arr = {1, 0, 2, 3, 2, 0, 0, 4, 5, 1};
int n = 10;
vector<int> ans = moveZeros(n, arr);
for (auto &it : ans) {
cout << it << " ";
}
cout << '\n';
return 0;
}
```
```
``````

import java.util.*;

public class tUf {
public static int[] moveZeros(int n, int []a) {
int j = -1;
//place the pointer j:
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
j = i;
break;
}
}

//no non-zero elements:
if (j == -1) return a;

//Move the pointers i and j
//and swap accordingly:
for (int i = j + 1; i < n; i++) {
if (a[i] != 0) {
//swap a[i] & a[j]:
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
j++;
}
}
return a;
}

public static void main(String[] args) {
int[] arr = {1, 0, 2, 3, 2, 0, 0, 4, 5, 1};
int n = 10;
int[] ans = moveZeros(n, arr);
for (int i = 0; i < n; i++) {
System.out.print(ans[i] + " ");
}
System.out.println("");
}
}

```
```
``````

def moveZeros(n: int,  a: [int]) -> [int]:
j = -1
# Place the pointer j
for i in range(n):
if a[i] == 0:
j = i
break

# No non-zero elements
if j == -1:
return a

# Move the pointers i and j and swap accordingly
for i in range(j + 1, n):
if a[i] != 0:
a[i], a[j] = a[j], a[i]
j += 1

return a

arr = [1, 0, 2, 3, 2, 0, 0, 4, 5, 1]
n = 10
ans = moveZeros(n, arr)
for it in ans:
print(it, end=' ')
print()

```
```
``````

function moveZeros(n, a) {
let j = -1;

// Place the pointer j
for (let i = 0; i < n; i++) {
if (a[i] === 0) {
j = i;
break;
}
}

// No non-zero elements
if (j === -1) return a;

// Move the pointers i and j and swap accordingly
for (let i = j + 1; i < n; i++) {
if (a[i] !== 0) {
[a[i], a[j]] = [a[j], a[i]];
j++;
}
}

return a;
}

let arr = [1, 0, 2, 3, 2, 0, 0, 4, 5, 1];
let n = 10;
let ans = moveZeros(n, arr);
console.log(ans.join(' '));

```
```

Output: 1 2 3 2 4 5 1 0 0 0

Complexity Analysis

Time Complexity: O(N), N = size of the array.
Reason: We have used 2 loops and using those loops, we are basically traversing the array once.

Space Complexity: O(1) as we are not using any extra space to solve this problem.

Video Explanation