Reorder Array of Red, Blue and Green balls

user_964408 0
Viewed 10151

In one of my interviews the interviewer asked me - An array of some size contains Red, Blue and Green balls all mixed up randomly. like RGBBBRRGGG, where RGB is for Red, Green and Blue.

What is the most optimal way to end up with an array like- RRRRGGGGBBBB i.e. all R's, all G's and all B's together.

I proposed converting all Red, Blue, Green to their ASCII values and then running the most efficient sorting algorithm on it. But he wasn't impressed . Any other more efficient solution to this problem ? with lowest space and time complexity ?

sorting algorithm
7 Answers

Python Solution

input = [1, 0, 2, 2, 1, 0, 1, 2, 0, 0, 2, 1, 2, 0, 0]

output = []
for i in input:
    if i == 0:
        output.insert(0, i)
    elif i == 2:
        output.append(i)
    else:
        if output.count(2) > 0:
            index = output.insert(output.index(2), i)
        else:
            output.append(i)

print(output)
user_119139790

This solution takes O(n):

def sort_Colors(arr):
    first = 0
    mid = 0
    last = len(arr)-1
    while mid <= last:
        if arr[mid] == 0:
            arr[first] , arr[mid] = arr[mid], arr[first]
            first += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:
            arr[mid], arr[last] = arr[last], arr[mid]
            last -= 1
    return arr

Input = [1, 2, 0, 1, 0, 1, 2, 0, 0, 0, 0]

Output = [0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2]

user_100365820
Related