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 ,1Output:1 ,2 ,3 ,4 ,1 ,0 ,0 ,0Explanation:All the zeros are moved to the end and non-negative integers are moved to front by maintaining orderExample 2:Input:1,2,0,1,0,4,0Output:1,2,1,4,0,0,0Explanation:All the zeros are moved to the end and non-negative integers are moved to front by maintaining order

**Practice:**

** Disclaimer**:

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

## Brute Force Approach

## Algorithm / Intuition

**Solution 1:**

**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)
temp.add(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.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:**

- First, using a loop, we will place the pointer j. If we don’t find any 0, we will not perform the following steps.
- After that, we will point i to index j+1 and start moving the pointer using a loop.
- While moving the pointer i, we will do the following:
**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.

- 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

Special thanks toplease check out this articleSai bargav NellepalliandKRITIDIPTA GHOSHfor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,