Move all zeros present in the array to the end

Given an array of integers, move all zeros present in the array to the end. The solution should maintain the relative order of items in the array.

 

For example,


Input:  { 6, 0, 8, 2, 3, 0, 4, 0, 1 }

Output: { 6, 8, 2, 3, 4, 1, 0, 0, 0 }

 

The idea is very simple. If the current element is non-zero, we can place the element at next available position in the array. After all elements in the array are processed, we fill all remaining indices by 0.

This is demonstated below in C++ –

 

Download   Run Code

Output:

6 8 2 3 4 1 0 0 0

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 


 

Using partitioning logic of quicksort

We can also solve this problem in one scan of array by modifying partitioning logic of quicksort. The idea is to use 0 as a pivot element and make one pass of partition process. The partitioning logic will read all elements and each time we encounter a non-pivot element, that element is swapped with the first occurrence of pivot.

 
C++ implementation –
 

Download   Run Code

Output:

6 8 2 3 4 1 0 0 0

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Exercise: Modify the solution so that all 1’s would come first.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz