# 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

Output:

6 8 2 3 4 1 0 0 0

## Java

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

Output:

6 8 2 3 4 1 0 0 0

## Java

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.

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂