Open In App

Move all zeros to end of array

Last Updated : 18 Feb, 2025
Suggest changes
Share
Like Article
Like
Report

Given an array of integers arr[], the task is to 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: arr[] = [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: arr[] = [10, 20, 30]
Explanation: No change in array as there are no 0s.

Input: arr[] = [0, 0]
Output: arr[] = [0, 0]
Explanation: No change in array as there are all 0s.

Table of Content

[Naive Approach] Using Temporary Array - O(n) Time and O(n) Space

The idea is to create a temporary array of same size as the input array arr[].

  • First, copy all non-zero elements from arr[] to the temporary array.
  • Then, fill all the remaining positions in temporary array with 0.
  • Finally, copy all the elements from temporary array to arr[].

Working:

C++ 
// C++ Program to move all zeros to end using temporary array #include <bits/stdc++.h> using namespace std; // function to move all zeros to the end 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);  // Print the modified array  for (int num : arr) {  cout << num << " ";  }  return 0; }
C 
// C Program to move all zeros to end using temporary array #include <stdio.h> // function to move all zeros to the end 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);  // Print the modified array  for (int i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  return 0; }
Java 
// Java Program to move all zeros to end using temporary array import java.util.Arrays; class GfG {    // function to move all zeros to the end  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);  // Print the modified array  for (int num : arr) {  System.out.print(num + " ");  }  } }
Python 
# Python Program to move all zeros to the end # function to move all zeroes to the end 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) # Print the modified array for num in arr: print(num, end=" ")
C# 
// C# Program to move all zeros to end using temporary array using System; class GfG {    // function to move all zeros to the end  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 + " ");  } }
JavaScript 
// JavaScript Program to move all zeros to end using temporary array // function to move all zeros to the end 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]; } const arr = [1, 2, 0, 4, 3, 0, 5, 0]; pushZerosToEnd(arr); // Print the modified array console.log(arr.join(" "));

Output
1 2 4 3 5 0 0 0

[Better Approach] Two Traversals

The idea is to move all the zeros by traversing the array twice.

First Traversal: Shift non-zero elements

  • Traverse the array and maintain the count of non-zero elements. This count is initialized with 0 and keeps track of where the next non-zero element should be placed in the array.
  • If the element is non-zero, place it at arr[count] and increment count by 1.
  • After traversing all the elements, all non-zero elements will be shifted to the front while maintaining their original order.

Second Traversal: Fill remaining positions with zeros

  • After the first traversal, all non-zero elements will be at the start of the array and count will store the index where the first zero should be placed.
  • Iterate from count to the end of array and fill all indices with 0.

Working:

C++ 
// C++ Program to move all zeros to end using two traversals #include <bits/stdc++.h> using namespace std; // Function which pushes all zeros to end  void pushZerosToEnd(vector<int>& arr) {    // Count of non-zero elements  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; }
C 
// C Program to move all zeros to end using two traversals #include <stdio.h> // Function which pushes all zeros to end  void pushZerosToEnd(int* arr, int n) {    // Count of non-zero elements  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; }
Java 
// Java Program to move all zeros to end using two traversals class GfG {  // Function which pushes all zeros to end of an array  static void pushZerosToEnd(int[] arr) {    // Count of non-zero elements  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 + " ");  }  } }
Python 
# Python Program to move all zeros to end using two traversals # Function which pushes all zeros to end def pushZerosToEnd(arr): # Count of non-zero elements 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=" ")
C# 
// C# Program to move all zeros to end using two traversals using System; class GfG {  // Function which pushes all zeros to end of an array  static void pushZerosToEnd(int[] arr) {    // Count of non-zero elements  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 + " ");  }  } }
JavaScript 
// JavaScript Program to move all zeros to end using two traversals // Function which pushes all zeros to end of an array function pushZerosToEnd(arr) {    // Count of non-zero elements  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

Time Complexity: O(n), as we are traversing the array only twice.
Auxiliary Space: O(1)

[Expected Approach] One Traversal

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:

C++ 
// C++ Program to move all zeros to end using one traversal #include <bits/stdc++.h> using namespace std; // Function which pushes all zeros to end of array 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; }
C 
// C Program to move all zeros to end using one traversal #include <stdio.h> // Function which pushes all zeros to end of array 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; }
Java 
// Java Program to move all zeros to end using one traversal import java.util.Arrays; class GfG {  // Function which pushes all zeros to end of array  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 + " ");  }  } }
Python 
# Python Program to move all zeros to end using one traversal # Function which pushes all zeros to end of array 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=" ")
C# 
// C# Program to move all zeros to end using one traversal using System; class GfG {    // Function which pushes all zeros to end of array  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 + " ");  }  } }
JavaScript 
// JavaScript Program to move all zeros to end using one traversal // Function which pushes all zeros to end of array 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++;  }  } } 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

Time Complexity: O(n), as we are traversing the array only once.
Auxiliary Space: O(1)

[Another Approach] Using Library Methods

In C++, there exists a method stable_parition() that we can directly use here to implement the above method.

C++ 
// C++ Program to move zeros to the end using Library Methods #include <algorithm> #include <iostream> #include <vector> using namespace std; void pushZerosToEnd(vector<int> &arr) {  stable_partition(arr.begin(), arr.end(), [](int n) {   return n != 0; }); } int main() {  vector<int> arr = {1, 2, 0, 4, 3, 0, 5, 0};  pushZerosToEnd(arr);  for (int i : arr)  cout << i << ' ';  return 0; }

Output
1 2 4 3 5 0 0 0



Next Article
Rearrange array such that even positioned are greater than odd

K

kartik

Similar Reads

Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy  Cookies are not collected in the GeeksforGeeks mobile applications.
Lightbox