Move all zeros present in an array to the end

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 non-zero elements toward the left where elements zero are present. And in the second traversal, we will shift fill the remaining indices with 0.

Algorithm

1. Initialize an identifier pos=0 that will represent the index value for the next available position.
2. Traverse through every array element using a loop.
3. Inside the loop, check if the element is a non-zero element.
4. If the element is a non-zero element, put the element at arr[pos] and increase the value of pos by 1 (this will shift all the non-zero elements toward the left).
5. Now run a loop from pos to the end of the array and fill the remaining pos 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 non-zero
		//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 non-zero
        # 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 non-zero element with the first occurrence of the pivot (0 elements). With this, we will move all the non-zero elements toward the left side of the pivot element (0).

Algorithm

1. Initialize a pos identifier with index value 0, that will store the index value for the available next zero position.
2. Create a loop that will traverse through every element of the array.
3. Inside the loop check if the element is non-zero.
4. If the element is non-zero 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 non-zero
		//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 non-zero
        # 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 in-place
• 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