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 and Java –

C

Download   Run Code

Output:

6 8 2 3 4 1 0 0 0

Java

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

Download   Run Code

Output:

6 8 2 3 4 1 0 0 0

Java

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Anton
Guest
Anton

It’s possible to.track the index of last seen zero (z), and swap its value with any following non zero element (at index i), then simply increment the index of last seen zero: there’s either no elements between z and I, or they are all zeros.

https://ideone.com/9Xcc9y