Move all zeros to front of array
Given an array arr[] of integers, the task is to move all the zeros to the front of the array while preserving the order of non-zero elements. Modify the given array inplace.
Examples:
Input: arr[] = {1, 0, 20, 4, 3, 0, 0, 5}
Output: 0 0 0 1 20 4 3 5Input: arr[] = {1, 0, 2, 0, 3, 0}
Output: 0 0 0 1 2 3
Move all zeros to front of array using Linear Space O(N):
We can solve this problem by taking another array to store the non-zero numbers of the input array. Also, count the number of zeros present in the input array. Then, we can start filling the input array from the beginning with zeros and then fill the remaining array with non-zero numbers from the temp array.
Step-by-step algorithm:
- Initialize an empty list, say temp.
- Traverse through the array arr[] and insert/push all the non-zero elements into the temp list.
- Count the number of the zeros and store in count variable in the given array arr[].
- Modify the given array. Place count number of zeros in the beginning of the array arr[].
- Now replace the remaining elements of the array with the elements stored in temp list.
Below is the implementation of the algorithm:
#include <iostream>
#include <vector>
void pushZerosToFront(int arr[], int n) {
// Initializing a vector to store non-zero elements
std::vector<int> temp;
// Initializing count to count the number of zeros
int count = 0;
// Traverse through arr to store all non-zero elements into temp and count the zeros
for (int i = 0; i < n; ++i) {
if (arr[i] != 0) {
temp.push_back(arr[i]);
} else {
count += 1;
}
}
// Modify the array with count number of zeros
for (int i = 0; i < count; ++i) {
arr[i] = 0;
}
// Modifying remaining array elements with non-zero elements of temp
int k = 0;
for (int i = count; i < n; ++i) {
arr[i] = temp[k];
k += 1;
}
// Print the modified array
for (int i = 0; i < n; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {1, 0, 2, 0, 3, 0};
int n = sizeof(arr) / sizeof(arr[0]);
pushZerosToFront(arr, n);
return 0;
}
// This code is contributed by Ayush Mishra
import java.util.ArrayList;
import java.util.List;
public class PushZerosToFront {
public static void main(String[] args)
{
int[] arr = { 1, 0, 2, 0, 3, 0 };
// Initializing an ArrayList to store non-zero
// elements
List<Integer> temp = new ArrayList<>();
// Initializing count to count the number of zeros
int count = 0;
// Traverse through arr to store all non-zero
// elements into temp and count the zeros
for (int x : arr) {
if (x != 0) {
temp.add(x);
}
else {
count += 1;
}
}
// Modify the array with count number of zeros
for (int i = 0; i < count; i++) {
arr[i] = 0;
}
// Modifying remaining array elements with non-zero
// elements of temp
int k = 0;
for (int i = count; i < arr.length; i++) {
arr[i] = temp.get(k);
k += 1;
}
// Print the modified array
for (int x : arr) {
System.out.print(x + " ");
}
}
}
// This code is contributed by Shivam
# Python program to push zeros to the front
arr = [1, 0, 2, 0, 3, 0]
# Initializing an empty list temp
temp = []
# Initializing count to count the number of zeros
count = 0
# Traverse through arr to store all non - zero elements into temp and count the zeros
for x in arr:
if x != 0:
temp.append(x)
else:
count += 1
# Modify the array with count number of zeros
for i in range(count):
arr[i] = 0
# Modifying remaining array elements with non-zero elements of temp
k = 0
for i in range(count, len(arr)):
arr[i] = temp[k]
k += 1
for x in arr:
print(x, end=" ")
function pushZerosToFront(arr) {
// Initializing an array to store non-zero elements
let temp = [];
// Initializing count to count the number of zeros
let count = 0;
// Traverse through arr to store all non-zero elements into temp and count the zeros
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0) {
temp.push(arr[i]);
} else {
count += 1;
}
}
// Modify the array with count number of zeros
for (let i = 0; i < count; i++) {
arr[i] = 0;
}
// Modifying remaining array elements with non-zero elements of temp
for (let i = count, k = 0; i < arr.length; i++, k++) {
arr[i] = temp[k];
}
// Print the modified array
console.log(arr);
}
const arr = [1, 0, 2, 0, 3, 0];
pushZerosToFront(arr);
// This code is contributed by Shivam
Output
0 0 0 1 2 3
Time Complexity: O(n), where n is number of elements in input array.
Auxiliary Space: O(k), where k is number of non-zero elements
Move all zeros to front of array using Constant Space O(1):
We can solve the problem by maintaining a pointer to the last zero of the array, say end and then start iterating from the pointer to the beginning. If at any index i we find a non-zero value, we swap the arr[i] with arr[end] and decrement the end by 1. Here end always points to last zero in the array arr[].
Step-by-step algorithm:
- Traverse the array arr[] from the end and find the index of last zero in the arr[], store it in a variable say end.
- Now, start traversing from end-1 to 0.
- While traversing, if the element in the array arr[] is not equal to zero, swap it with arr[end].
- After swapping, decrement the value of end.
- Repeat the above steps till we have traversed all the elements from end to 0.
Below is the implementation of the algorithm:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {1, 0, 2, 0, 3, 0};
// Finding the length of the array
int n = arr.size();
// Find the index of the last zero
int end = -1;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] == 0) {
end = i;
break;
}
}
// Modifying the array by traversing from end-1 to 0
for (int i = end - 1; i >= 0; i--) {
if (arr[i] != 0) { // If element is a non-zero element, swap it with arr[end]
int temp = arr[i];
arr[i] = arr[end];
arr[end] = temp;
end--;
}
}
// Printing the array after pushing all zeros to the front
for (int x : arr) {
cout << x << " ";
}
return 0;
}
public class Main {
public static void main(String[] args)
{
int[] arr = { 1, 0, 2, 0, 3, 0 };
// finding length of the array
int n = arr.length;
// find the index of last zero
int end = -1;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] == 0) {
end = i;
break;
}
}
// Modifying the array by traversing from end-1 to 0
for (int i = end - 1; i >= 0; i--) {
if (arr[i]
!= 0) { // if element is a non-zero element,
// swap it with arr[end]
int temp = arr[i];
arr[i] = arr[end];
arr[end] = temp;
end--;
}
}
// printing the array after pushing all zeros to the
// front
for (int x : arr) {
System.out.print(x + " ");
}
}
}
// This code is contributed by Shivam
arr = [1, 0, 2, 0, 3, 0]
# finding length of the array
n = len(arr)
# find the index of last zero
end = -1
for i in range(n-1, -1, -1):
if(arr[i] == 0):
end = i
break
# Modifying the array by traversing from end-1 to 0
for i in range(end-1, -1, -1):
if(arr[i] != 0): # if element is a non-zero element, swap it with arr[end]
temp = arr[i]
arr[i] = arr[end]
arr[end] = temp
end -= 1
# printing the array after pushing all zeros to the front
for x in arr:
print(x, end=" ")
function main() {
let arr = [1, 0, 2, 0, 3, 0];
// finding length of the array
let n = arr.length;
// find the index of last zero
let end = -1;
for (let i = n - 1; i >= 0; i--) {
if (arr[i] === 0) {
end = i;
break;
}
}
// Modifying the array by traversing from end-1 to 0
for (let i = end - 1; i >= 0; i--) {
if (arr[i] !== 0) { // if element is a non-zero element,
// swap it with arr[end]
let temp = arr[i];
arr[i] = arr[end];
arr[end] = temp;
end--;
}
}
// printing the array after pushing all zeros to the
// front
for (let x of arr) {
console.log(x + " ");
}
}
main();
Output
0 0 0 1 2 3
Time Complexity: O(n), n is number of elements in the input array.
Auxiliary Space: O(1)
Contact Us