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
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 to Sai bargav Nellepalli and KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article