We have given an integer array, and we need to move all the zeros present in it to the end. And the output array must maintain the relative order of its elements, which means the order of other elements (except 0) must be in the same order.
Example
Input : [5,0,7,4,5,3,0,1,0,6] Output: [5,7,4,5,3,1,6,0,0,0]
Explanation In the output, you can see that all the zeros have been moved to the end of the array, and the order of the rest of the elements is the same.
Approach 1
Optimized Algorithm
In this approach, we will use two loops to solve the problem. In the first traversal, we will traverse through the complete array, check if the current element is not zero, then place the element at the available position in the array. The idea is simple we will shift all the nonzero elements toward the left where elements zero are present. And in the second traversal, we will shift fill the remaining indices with 0.
Algorithm

Initialize an identifier
pos=0
that will represent the index value for the next available position.  Traverse through every array element using a loop.
 Inside the loop, check if the element is a nonzero element.

If the element is a nonzero element, put the element at
arr[pos]
and increase the value ofpos
by 1 (this will shift all the nonzero elements toward the left). 
Now run a loop from
pos
to the end of the array and fill the remainingpos
indices with zeros.
C++ Programming
#include <iostream> using namespace std; // function to move zeros //at the end of the array void move_zeros(int arr[],int n) { //pos will store the index value //for the next available position int pos =0; //traverse through every element for(int i=0; i<n;i++) { //check if the current element is nonzero //put the element at the arr[pos] if (arr[i]!=0) { arr[pos]=arr[i]; pos++; } } //fill the remaining pos indices with zeros for(int i=pos; i<n; i++) { arr[i]=0; } } int main() { //given array int arr[]={5,0,7,4,5,3,0,1,0,6}; //length of the array int n = sizeof(arr) / sizeof(arr[0]); move_zeros(arr, n); for(int i=0; i<n;i++) { cout<<arr[i]<<" "; } return 0; }
Output
Python Programming
def move_zeros(arr, n): # pos will store the index value # for the next available position pos=0 # traverse through every element for i in arr: # check if the current element is nonzero # put the element at the arr[pos] if i: arr[pos]=i pos+=1 #fill the remaining pos indices with zeros for i in range(pos, n): arr[i]=0 if __name__=="__main__": #given array arr= [5,0,7,4,5,3,0,1,0,6 ] #length of array n = len(arr) move_zeros(arr,n) print(arr)
Output
Complexity Analysis
 Time Complexity: O(N), is the time complexity of the above program.
 Space Complexity: The space complexity is O(1) because we did not use any extra array to store given array elements.
Approach 2
Using Quick Sort Pivot Logic
This problem can also be solved using the same quick sort algorithm partitioning logic. Here, we will use the 0 elements as a pivot element, traverse through the array, and swap every nonzero element with the first occurrence of the pivot (0 elements). With this, we will move all the nonzero elements toward the left side of the pivot element (0).
Algorithm

Initialize a
pos
identifier with index value 0, that will store the index value for the available next zero position.  Create a loop that will traverse through every element of the array.
 Inside the loop check if the element is nonzero.
 If the element is nonzero swap the elements with arr[pos], and increment the value of pos by 1.
C++ Programming
#include <iostream> using namespace std; // function to move zeros //at the end of the array void move_zeros(int arr[],int n) { // initialize position identifier int pos=0; // initialize temp variable for swapping int temp; //traverse through every element for(int i=0; i<n; i++) { //check if the element is nonzero //swap the element with arr[pos] //increase the pos value by 1 if(arr[i]!=0) { temp = arr[i]; arr[i]= arr[pos]; arr[pos] = temp; pos++; } } } int main() { //given array int arr[]={5,0,7,4,5,3,0,1,0,6}; //length of the array int n = sizeof(arr) / sizeof(arr[0]); move_zeros(arr, n); for(int i=0; i<n;i++) { cout<<arr[i]<<" "; } return 0; }
Output
Python Programing
def move_zeros(arr, n): #initialize position identifier pos= 0 for i in range(n): # check if the element is nonzero # swap the element with arr[pos] # increase the pos value by 1 if arr[i]: arr[i],arr[pos] = arr[pos], arr[i] pos+=1 if __name__=="__main__": #given array arr= [5,0,7,4,5,3,0,1,0,6 ] #length of array n = len(arr) move_zeros(arr,n) print(arr)
Output
Complexity Analysis
 Time Complexity: O(N ) is the time complexity of the above program.
 Space Complexity: O(1)
Wrapping Up!
In this DSA tutorial, we learned two different algorithms to "Move all zeros present in an array to the end". We not only discuss the algorithms but also implement both the algorithms in C++ and Python programming languages. There are many other logic and algorithms we can use to solve this problem, but the above two are the most optimized and solve the problem in linear time complexity with Constant space complexity.
If you like this article or want to share your feedback, please let us know by commenting down below.
People are also reading:
 Merge Two Sorted Arrays inplace
 Print all subarrays with 0 sum
 Longest subarray with sum as K
 Rearrange an array in maximum minimum form
 Find whether an array is subset of another array
 Rod Cutting Problem – Dynamic Programming
 Print a given matrix in spiral form
 Maximum of all Subarrays of size K
 Program to Rotate an Array
 Sort binary array in linear time
Leave a Comment on this Post