Reorder Array of Red, Blue and Green balls

Question

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 ?

Answer 1

Simply go through the array and count the occurrence of R, G and B respectively. Then, output the string. Linear time.

Answer 2

The interviewer might have wanted to know if you were familiar with the Dutch national flag problem. It has a simple linear solution. There are C++ and Java examples on the Wikipedia page.