RGB Partition Swap Problem

This problem is a hard one asked by Google.

Problem Statement

Given an array of strictly the characters 'R', 'G', and 'B', segregate the values of the array so that all the Rs come first, the Gs come second, and the Bs come last. You can only swap elements of the array.

You are asked to do this in linear time and in-place. Given input [G, B, R, R, B, R, G] the output is [R, R, R, G, G, B, B].

Intuition

When approaching this problem we can first observe that we know that all R must go to the beginning of the array and all B must go to the end of the array. Since we must do swaps in linear time and in-place we must have a running time of O(N) with constant space.

Consider each character approached in the sequence. If we maintain the invariant that all elements to the left of the index we’re currently looking at all contain R and all elements from the end of the array contain B then it must be the case that the elements in the middle are all G.

As it turns out, this is basically the solution. It’s a two-pointer technique with a variable representing the low index, middle index and high index. Whenever we see a red or blue we can swap it with the lower index, increment low and if we see blue we can swap it with the high index and decrement high.

So the goal is to reach the middle where low > high then we have that the low and high partitions as well as middle are sorted and terminate.

Conclusion

I think this is a really clever problem with a clever solution that stems from maintaining invariants on the problem at each step. See this StackOverflow post for more details.

It’s sort of like the median of data stream problem insofar as thinking of it at each step in terms of some other abstract concept (in this case partitions) helps you solve it.

Back