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