Sort binary array in linear time

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 vice-versa by counting the number of 1's and put that number of ones at the end of the array.

Algorithm

1. Count the number of zeros present in the binary array as count_zeroes.
2. Run a loop from index 0 to count_zeroes and replace that indexes elements of the binary array with 0.
3. 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

1. Initialize two pointers i with index value 0 and j with index value n-1 .
2. Also, initialize a temp variable for swapping.
3. Create a while loop with condition i < j, that will keep iterating till i<j.
4. Inside the loop set an if condition that will execute if arr[i] ==1 , and it will swap the array index i element with array index j element, and decrease the j pointer by 1 j-- .
5. 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= n-1;
    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=n-1

   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 if-else 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 sub-matrices 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