Move all zeros present in an array to the end

Posted in

Move all zeros present in an array to the end
vinaykhatri

Vinay Khatri
Last updated on March 29, 2024

    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:

    Leave a Comment on this Post

    0 Comments