# Sort Binary Array in Linear Time

Given an binary array, sort it in linear time and constant space. Output should print contain all zeroes followed by all ones.

For example,

Input: { 1, 0, 1, 0, 1, 0, 0, 1 }

Output:{ 0, 0, 0, 0, 1, 1, 1, 1 }

Simple solution would be to count number of 0’s present in the array (say k) and fill first k indices in the array by 0 and all remaining indices by 1.

Alternatively, we can also count number of 1’s present in the array (say k) and fill last k indices in the array by 1 and all remaining indices by 0.

## Java

Output:

0 0 0 0 0 0 1 1 1 1

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

Instead of counting number of zeroes, if the current element is 0, we can place 0 at next available position in the array. After all elements in the array are processed, we fill all remaining indices by 1.

## Java

Output:

0 0 0 0 0 0 1 1 1 1

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

We can also solve this problem in linear time by using partitioning logic of quicksort. The idea is to use 1 as pivot element and make one pass of partition process. The resultant array will be sorted.

## Java

Output:

0 0 0 0 1 1 1 1

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

Exercise:

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

2. Rearrange even and odd numbers in an array in linear time such that all even numbers comes before all odd numbers.

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 🙂

Subscribe
Notify of
Guest
Shubham Mathur
Guest
Vishwajeet

Nice Method of Partititioning

Guest

Guest

Time complexity is O(n)

Guest
clankill3r

Guest

Hi, I didn’t get the concept of placing a zero in the next available position in the second proposed solution. What do you mean by next available position? Isn’t the array full of 0’s and 1’s??

Guest