Given an array of integers arr[], move all the zeros to the end of the array while maintaining the relative order of all non-zero elements.
Examples:
Input: arr[] = [1, 2, 0, 4, 3, 0, 5, 0]
Output: [1, 2, 4, 3, 5, 0, 0, 0]
Explanation: There are three 0s that are moved to the end.Input: arr[] = [10, 20, 30]
Output: [10, 20, 30]
Explanation: No change in array as there are no 0s.Input: arr[] = [0, 0]
Output: [0, 0]
Explanation: No change in array as there are all 0s.
Try it on GfG Practice
Table of Content
[Naive Approach] Using Temporary Array - O(n) Time and O(n) Space
The idea is to use a temporary array of the same size, copy all non-zero elements into it, fill the remaining positions with zeros, and then copy the temporary array back to the original array.
Working:
#include <iostream>
#include <vector>
using namespace std;
void pushZerosToEnd(vector<int> &arr)
{
int n = arr.size();
vector<int> temp(n);
// to keep track of the index in temp[]
int j = 0;
// Copy non-zero elements to temp[]
for (int i = 0; i < n; i++)
{
if (arr[i] != 0)
temp[j++] = arr[i];
}
// Fill remaining positions in temp[] with zeros
while (j < n)
{
temp[j++] = 0;
}
// Copy all the elements from temp[] to arr[]
for (int i = 0; i < n; i++)
arr[i] = temp[i];
}
int main()
{
vector<int> arr = {1, 2, 0, 4, 3, 0, 5, 0};
pushZerosToEnd(arr);
for (int num : arr)
{
cout << num << " ";
}
return 0;
}
#include <stdio.h>
void pushZerosToEnd(int *arr, int n)
{
int temp[n];
// to keep track of the index in temp[]
int j = 0;
// Copy non-zero elements to temp[]
for (int i = 0; i < n; i++)
{
if (arr[i] != 0)
temp[j++] = arr[i];
}
// Fill remaining positions in temp[] with zeros
while (j < n)
temp[j++] = 0;
// Copy all the elements from temp[] to arr[]
for (int i = 0; i < n; i++)
arr[i] = temp[i];
}
int main()
{
int arr[] = {1, 2, 0, 4, 3, 0, 5, 0};
int n = sizeof(arr) / sizeof(arr[0]);
pushZerosToEnd(arr, n);
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
import java.util.Arrays;
class GfG {
static void pushZerosToEnd(int[] arr) {
int n = arr.length;
int[] temp = new int[n];
// to keep track of the index in temp[]
int j = 0;
// Copy non-zero elements to temp[]
for (int i = 0; i < n; i++) {
if (arr[i] != 0)
temp[j++] = arr[i];
}
// Fill remaining positions in temp[] with zeros
while (j < n)
temp[j++] = 0;
// Copy all the elements from temp[] to arr[]
for (int i = 0; i < n; i++)
arr[i] = temp[i];
}
public static void main(String[] args) {
int[] arr = {1, 2, 0, 4, 3, 0, 5, 0};
pushZerosToEnd(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
def pushZerosToEnd(arr):
n = len(arr)
temp = [0] * n
# to keep track of the index in temp[]
j = 0
# Copy non-zero elements to temp[]
for i in range(n):
if arr[i] != 0:
temp[j] = arr[i]
j += 1
# Fill remaining positions in temp[] with zeros
while j < n:
temp[j] = 0
j += 1
# Copy all the elements from temp[] to arr[]
for i in range(n):
arr[i] = temp[i]
if __name__ == "__main__":
arr = [1, 2, 0, 4, 3, 0, 5, 0]
pushZerosToEnd(arr)
for num in arr:
print(num, end=" ")
using System;
class GfG {
static void pushZerosToEnd(int[] arr)
{
int n = arr.Length;
int[] temp = new int[n];
// to keep track of the index in temp[]
int j = 0;
// Copy non-zero elements to temp[]
for (int i = 0; i < n; i++) {
if (arr[i] != 0)
temp[j++] = arr[i];
}
// Fill remaining positions in temp[] with zeros
while (j < n)
temp[j++] = 0;
// Copy all the elements from temp[] to arr[]
for (int i = 0; i < n; i++)
arr[i] = temp[i];
}
static void Main(string[] args)
{
int[] arr = { 1, 2, 0, 4, 3, 0, 5, 0 };
pushZerosToEnd(arr);
// Print the modified array
foreach(int num in arr) Console.Write(num + " ");
}
}
function pushZerosToEnd(arr)
{
const n = arr.length;
const temp = new Array(n);
// to keep track of the index in temp[]
let j = 0;
// Copy non-zero elements to temp[]
for (let i = 0; i < n; i++) {
if (arr[i] !== 0) {
temp[j++] = arr[i];
}
}
// Fill remaining positions in temp[] with zeros
while (j < n)
temp[j++] = 0;
// Copy all the elements from temp[] to arr[]
for (let i = 0; i < n; i++)
arr[i] = temp[i];
}
// Driver Code
const arr = [ 1, 2, 0, 4, 3, 0, 5, 0 ];
pushZerosToEnd(arr);
console.log(arr.join(" "));
Output
1 2 4 3 5 0 0 0
[Better Approach] Two Traversals-O(n) Time and O(1) space
The idea is to move all the zeros to the end of the array while maintaining the relative order of non-zero elements using two traversals. Traverse the array once to move all non-zero elements to the front while maintaining order, then traverse the remaining positions and fill them with zeros.
Working:
#include <iostream>
#include <vector>
using namespace std;
void pushZerosToEnd(vector<int> &arr)
{
int count = 0;
// If the element is non-zero, replace the element at
// index 'count' with this element and increment count
for (int i = 0; i < arr.size(); i++)
{
if (arr[i] != 0)
arr[count++] = arr[i];
}
// Now all non-zero elements have been shifted to
// the front. Make all elements 0 from count to end.
while (count < arr.size())
arr[count++] = 0;
}
int main()
{
vector<int> arr = {1, 2, 0, 4, 3, 0, 5, 0};
pushZerosToEnd(arr);
for (int num : arr)
{
cout << num << " ";
}
return 0;
}
#include <stdio.h>
void pushZerosToEnd(int *arr, int n)
{
int count = 0;
// If the element is non-zero, replace the element at
// index 'count' with this element and increment count
for (int i = 0; i < n; i++)
{
if (arr[i] != 0)
arr[count++] = arr[i];
}
// Now all non-zero elements have been shifted to
// the front. Make all elements 0 from count to end.
while (count < n)
arr[count++] = 0;
}
int main()
{
int arr[] = {1, 2, 0, 4, 3, 0, 5, 0};
int size = sizeof(arr) / sizeof(arr[0]);
pushZerosToEnd(arr, size);
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
class GfG {
static void pushZerosToEnd(int[] arr)
{
int count = 0;
// If the element is non-zero, replace the element
// at index 'count' with this element and increment
// count
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0)
arr[count++] = arr[i];
}
// Now all non-zero elements have been shifted to
// the front. Make all elements 0 from count to end.
while (count < arr.length)
arr[count++] = 0;
}
public static void main(String[] args)
{
int[] arr = { 1, 2, 0, 4, 3, 0, 5, 0 };
pushZerosToEnd(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
def pushZerosToEnd(arr):
count = 0
# If the element is non-zero, replace the element at
# index 'count' with this element and increment count
for i in range(len(arr)):
if arr[i] != 0:
arr[count] = arr[i]
count += 1
# Now all non-zero elements have been shifted to
# the front. Make all elements 0 from count to end.
while count < len(arr):
arr[count] = 0
count += 1
if __name__ == "__main__":
arr = [1, 2, 0, 4, 3, 0, 5, 0]
pushZerosToEnd(arr)
for num in arr:
print(num, end=" ")
using System;
class GfG {
static void pushZerosToEnd(int[] arr)
{
int count = 0;
// If the element is non-zero, replace the element
// at index 'count' with this element and increment
// count
for (int i = 0; i < arr.Length; i++) {
if (arr[i] != 0)
arr[count++] = arr[i];
}
// Now all non-zero elements have been shifted to
// the front. Make all elements 0 from count to end.
while (count < arr.Length)
arr[count++] = 0;
}
static void Main()
{
int[] arr = { 1, 2, 0, 4, 3, 0, 5, 0 };
pushZerosToEnd(arr);
foreach(int num in arr)
{
Console.Write(num + " ");
}
}
}
function pushZerosToEnd(arr)
{
let count = 0;
// If the element is non-zero, replace the element at
// index 'count' with this element and increment count
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0)
arr[count++] = arr[i];
}
// Now all non-zero elements have been shifted to
// the front. Make all elements 0 from count to end.
while (count < arr.length)
arr[count++] = 0;
}
// Driver Code
const arr = [ 1, 2, 0, 4, 3, 0, 5, 0 ];
pushZerosToEnd(arr);
console.log(arr.join(" "));
Output
1 2 4 3 5 0 0 0
[Expected Approach] One Traversal-O(n) Time and O(1) space
The idea is similar to the previous approach where we took a pointer, say count to track where the next non-zero element should be placed. However, on encountering a non-zero element, instead of directly placing the non-zero element at arr[count], we will swap the non-zero element with arr[count]. This will ensure that if there is any zero present at arr[count], it is pushed towards the end of array and is not overwritten.
Working:
#include <iostream>
#include <vector>
using namespace std;
void pushZerosToEnd(vector<int>& arr) {
// Pointer to track the position
// for next non-zero element
int count = 0;
for (int i = 0; i < arr.size(); i++) {
// If the current element is non-zero
if (arr[i] != 0) {
// Swap the current element with
// the 0 at index 'count'
swap(arr[i], arr[count]);
// Move 'count' pointer to the
// next position
count++;
}
}
}
int main() {
vector<int> arr = {1, 2, 0, 4, 3, 0, 5, 0};
pushZerosToEnd(arr);
for (int num : arr) {
cout << num << " ";
}
return 0;
}
#include <stdio.h>
void pushZerosToEnd(int arr[], int n) {
// Pointer to track the position
// for next non-zero element
int count = 0;
for (int i = 0; i < n; i++) {
// If the current element is non-zero
if (arr[i] != 0) {
// Swap the current element with
// the 0 at index 'count'
int temp = arr[i];
arr[i] = arr[count];
arr[count] = temp;
// Move 'count' pointer to
// the next position
count++;
}
}
}
int main() {
int arr[] = {1, 2, 0, 4, 3, 0, 5, 0};
int size = sizeof(arr) / sizeof(arr[0]);
pushZerosToEnd(arr, size);
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
import java.util.Arrays;
class GfG {
static void pushZerosToEnd(int[] arr) {
// Pointer to track the position
// for next non-zero element
int count = 0;
for (int i = 0; i < arr.length; i++) {
// If the current element is non-zero
if (arr[i] != 0) {
// Swap the current element with
// the 0 at index 'count'
int temp = arr[i];
arr[i] = arr[count];
arr[count] = temp;
// Move 'count' pointer to
// the next position
count++;
}
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 0, 4, 3, 0, 5, 0};
pushZerosToEnd(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
def pushZerosToEnd(arr):
# Pointer to track the position
# for next non-zero element
count = 0
for i in range(len(arr)):
# If the current element is non-zero
if arr[i] != 0:
# Swap the current element with
# the 0 at index 'count'
arr[i], arr[count] = arr[count], arr[i]
# Move 'count' pointer to the next position
count += 1
if __name__ == "__main__":
arr = [1, 2, 0, 4, 3, 0, 5, 0]
pushZerosToEnd(arr)
for num in arr:
print(num, end=" ")
using System;
class GfG {
static void pushZerosToEnd(int[] arr) {
// Pointer to track the position
// for next non-zero element
int count = 0;
for (int i = 0; i < arr.Length; i++) {
// If the current element is non-zero
if (arr[i] != 0) {
// Swap the current element with
// the 0 at index 'count'
int temp = arr[i];
arr[i] = arr[count];
arr[count] = temp;
// Move 'count' pointer to
// the next position
count++;
}
}
}
static void Main() {
int[] arr = { 1, 2, 0, 4, 3, 0, 5, 0 };
pushZerosToEnd(arr);
foreach (int num in arr) {
Console.Write(num + " ");
}
}
}
function pushZerosToEnd(arr) {
// Pointer to track the position
// for next non-zero element
let count = 0;
for (let i = 0; i < arr.length; i++) {
// If the current element is non-zero
if (arr[i] !== 0) {
// Swap the current element
// with the 0 at index 'count'
[arr[i], arr[count]] = [arr[count], arr[i]];
// Move 'count' pointer to the next position
count++;
}
}
}
// Driver code
const arr = [1, 2, 0, 4, 3, 0, 5, 0];
pushZerosToEnd(arr);
console.log(arr.join(" "));
Output
1 2 4 3 5 0 0 0