We have given a binary array (contains one 1s and 0s), and we need to write a logic that can sort the array with linear time O(N) and constant space O(1) time and space complexity, respectively. After sorting the array, all zeros must be followed by all ones.
Example 1
Input = [1,0,1,0,1,0,1,0,1,0] Output= [0,0,0,0,0,1,1,1,1,1]
Explanation
The problem statement is very straightforward, we have a binary array and we need to sort it. Although we can use any sorting algorithm to sort the binary array, but, all the sorting algorithms generally have time complexity more than O(N). So we need to come up with some algo or logic that can sort our binary array with linear time complexity and constant space complexity. This means we can not use any nested loop or create any new array to store the elements of the given binary array.
Approach 1
Naive Algo Sort binary array with multi traversal
In this approach, we will first count the number of zeroes present in the array. Let say the number of zeros is
count_zeroes
, then using the loop we will put that number of zeros in the first
count_zeroes
indexes of the array, and keep reset of the array elements as 1's. We can also do the viceversa by counting the number of 1's and put that number of ones at the end of the array.
Algorithm

Count the number of zeros present in the binary array as
count_zeroes.

Run a loop from index
0
tocount_zeroes
and replace that indexes elements of the binary array with 0.  And again run a loop that that that will replace the remaining elements of the binary array with 1.
CPP
#include <iostream> using namespace std; // function that will sort //the binary array in linear time complexity int sort_binary(int arr[], int n) { // count number of zeros int count_zeros = 0; for (int i = 0; i < n; i++) { if (arr[i] == 0) { count_zeros++; } } // replace all the first count_zeros elemets with 0 for(int i=0; i<count_zeros; i++) { arr[i] =0; } // fill remaining array elements by 1 for(int i=count_zeros; i<n; i++) { arr[i] =1; } } int main(void) { int arr[] = {1,0,1,0,1,0,1,0,1,0,1,0}; int n = sizeof(arr)/sizeof(arr[0]); sort_binary(arr, n); // print the sorted binary array for (int i = 0; i < n; i++) { cout<<arr[i]<<" "; } return 0; }
Output
Python
#function to sort the binary array def sort_binary(arr, n): """count the number of zeros present in the binary array""" count_zeros = arr.count(0) #replace all the first count_zeros elemets with 0 for i in range(count_zeros): arr[i]=0 #fill the remaining array elements by 1 for i in range(count_zeros, n): arr[i]=1 if __name__=="__main__": arr= [0,1,0,1,0,1,0,1,0,1] #len of array n = len(arr) sort_binary(arr,n) print(arr)
Output
Complexity Analysis:
Time Complexity: The time complexity of the above program is O(N), where N is the total number of elements present in the array. Although we are using multiple loops, still it has linear time complexity. Space Complexity: The Space complexity of the above program is O(1), because we are not using any new array, and all the changes were made on the real array object.
Approach 2:
Sort binary array with Single traversal
In the above approach, we used multiple loops to sort the array, but we can also have an algorithm that can sort the array in a single iteration or traversal. In this algorithm, we will have two pointers
i
and
j
, where
i
pointer points to the first index value of the array and
j
will point to the last index value of the array. If the
arr[i]
is equal to 1 we will swap the
arr[i]
with
arr[j]
and decrease te pointer
j
to
j
. Else if the
array[i]
is equal to 0 we will increase the pointer
i
by
i++
. This statement will keep running till i<j.
Algorithm

Initialize two pointers
i
with index value 0 andj
with index valuen1
. 
Also, initialize a
temp
variable for swapping.  Create a while loop with condition i < j, that will keep iterating till i<j.

Inside the loop set an
if
condition that will execute ifarr[i] ==1
, and it will swap the array index i element with array index j element, and decrease the j pointer by 1j
. 
In the else statement increases the
i
index value by 1 with i++.
CPP
#include <iostream> using namespace std; // function that will sort //the binary array in linear time complexity int sort_binary(int arr[], int n) { int i= 0; int j= n1; int temp; while(i<j) { // if the ith index element is 1 if(arr[i]==1) { // swap the i and j indexes elements // and decrease the j pointer temp =arr[i]; arr[i]=arr[j]; arr[j] =temp; j; } else //else if the ith index element is 0 //increment the ith index value i++; } } int main(void) { int arr[] = {1,0,1,0,1,0,1,0,1,0,1,0}; int n = sizeof(arr)/sizeof(arr[0]); sort_binary(arr, n); // print the rearranged array for (int i = 0; i < n; i++) { cout<<arr[i]<<" "; } return 0; }
Output
Python
#function to sort the binary array def sort_binary(arr, n): i=0 j=n1 while (i<j): #if the ith index element is 1 if arr[i]==1: #swap the i and j indexes elements #and decrease the j pointer arr[i], arr[j]= arr[j], arr[i] j=1 else: # else if the ith index element is 0 # increment the ith index value i+=1 if __name__=="__main__": arr= [0,1,0,1,0,1,0,1,0,1] #len of array n = len(arr) sort_binary(arr,n) print(arr)
Output
Complexity Analysis:
 Time Complexity: O(N) is the time complexity of the above program.
 Space Complexity: O(1), because we did not use any extra array to store the binary array elements.
Wrapping up!
Sort Binary Array is one of the most common DSA interview questions. And in this article, we learned two different approaches to sort a binary array. In both the approaches, we sort the array in Linear time complexity without using any extra array that results in constant space complexity too. In the first approach, we used multiple iterations to sort the array. Where we first count the number of zeros present in the array, fill the first indexes elements by zeros and the rest of the elements by 1.
In the second approach, we used swapping and single traversal to sort the binary array. Where we used two pointers, one at the beginning of the array and one at the end of the array. And using an ifelse condition we sorted the binary array.
People are also reading:
 WAP to Print Square Using * Character
 WAP to Print Triangle Using * Character
 Find ancestors of a given node in a Binary Tree
 Subset Sum Problem
 Clone a Singly Linked List
 Maximum size square submatrices with all 1’s
 Merge Sort for Linked Lists
 Check if a subarray with 0 sum exists or not
 Find a Pair with the Given Sum in an Array
 Data Structure Interview Questions
Leave a Comment on this Post