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)
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
Contact Us