Question 3

Given an unsorted binary array, you need to sort it in linear time – O(n) and constant space O(1).

Input: [0, 1, 1, 0, 1, 0, 0]

Output:[0, 0, 0, 0, 1, 1, 1]

Best Solution

Since the question clearly specifies that we sort in linear time and constant space, we simply would go directly to the solution.

The approach is this: Iterate through the array and each time you encounter a zero, move it to the beginning. At the same time, keep count of the number of zeroes seen so far. At the end of the iteration, then fill the remaining part of the array with ones.

This means that the total time taken is linear.

The Python code is given below:

# **** SORT A BINARY ARRAY IN LINEAR TIME AND CONSTANT SPACE ****

def sortBinaryArray(a):
    j = 0 # number of zeroes so far
    i = 0 # loop variable
    while(i != len(a)):
        if(a[i] == 0):
            a[j] = 0
            j = j + 1
        i = i + 1

    for i in range(j+1, len(a)):
        a[i] = 1

ar = [0, 1, 1, 0, 1, 0, 0]
print(ar)
sortBinaryArray(ar)
print(ar)