Dutch Flag Problem

Problem Definition – Dutch Flag Problem

The dutch flag looks like the below image.

The problem “Dutch Flag Problem” derives its name from the arrangement of colors in the flag. The actual problem definition goes like this:
Given an array of balls of three colors ( Red, White and Blue). The balls are kept in random positions in the array. We need to develop a mechanism which can arrange the balls in groups (based on colors). Below is the image of a possible input and the expected output.

The balls of different colors in the above image are randomly distributed in the input where as the output array contains the red group in the beginning, then the white group and at last the blue group.

Approach

Please note that this is not a generic solution for n colors, it can only be solved for three colors as in the Dutch Flag. The idea is to push all the red color balls in the beginning of the array and push all the blue color balls in the right of the array. The white balls will automatically fall in the center.

The basic thought is to define three sections red(in the beginning of the array), blue (in the end of the array) and white which should be in the middle. Then maintain three pointers as below:

• Pointer red which points to the first index of the array and moves one step to the right if a red ball is added in the red section.
• Pointer blue which points to the last index of the array and moves one step to the left if a blue ball is added in the blue section.
• Pointer white which points to the first index of the array and moves one step to the right each time.

In the start of the algorithm. It is possible that there is no elements in the red, white or blue section. So we point the red pointer at the first element in the array, we point the white pointer at the first element of the array and the blue pointer at the end. Consider the below image:

There are three cases which are possible:

• The white pointer is pointing to the red ball. In this case the red ball has to be pushed to the left. We achieve this by swapping the balls at red pointer and the white pointer. We end up swapping the same ball with itself in this case particular case ðŸ™‚ . Also, now the red and the white pointer must move to the right to proceed further.
• The white pointer is pointing to the white ball. This means that the white ball is at the correct position and only the white pointer should move to the right.
• The white pointer is pointing to the blue ball. In this case we need to push the blue ball to the extreme right. We achieve this by swapping the balls at the blue pointer and the white pointer. Now because the blue is at the right place, the blue pointer must move one space to the left.

We shall repeat this procedure till the blue pointer either coincides with the white pointer or comes to the left of the white pointer.

Hence in the above image, the red and white pointer are both at the same ball and the ball is red. So we swap the ball with itself and then move the pointers to the right to get the following image:

Now the white pointer is pointing to a blue ball, hence we need to push the ball in the extreme right, so we will swap the balls at the white pointer and the blue pointer. And we must move the blue pointer to the left by one. It will result in the below image:

Now the white pointer is pointing to a red ball, so we need to swap it with the ball at the red pointer and then move the red and the white pointer to the right. And the state of the system is represented by the below image:

Again the white pointer is pointing to the blue ball so we follow the same strategy as we followed above for the blue ball. So we swap the ball at the blue pointer with the ball at white pointer. Also, we move the blue pointer by one to the left. The positions of the ball will look as below:

Now the white pointer points at a white ball, so we just move the white pointer to the right by one. And the system looks like the below image:

Even in this state, the white pointer points to a white ball, so we just move the white pointer to the right by one step and it looks like below:

The state now shows that the white pointer is pointing to a blue ball. So we can again swap the balls at the white and blue pointer and move the blue pointer to the left by one step. Here are the new positions:

Now the white pointer points to a red ball, so we can just swap the balls at the red and white pointer and move both the pointers by one to the right. And the array looks like below.

Now we notice that the blue and the white pointer are at the same place and this is the termination condition for our algorithm as highlighted above.

Also, looking at this image shows that the dutch flag is now prepared.

Here is the source code in java with appropriate comments. Here for simplicity we assume the array to be filled with the numbers 1, 2 and 3. Also, please note that it is not necessary to have equal number of balls of each color. So the array below may not have equal numbers of 1, 2 and 3. We also assume that 1 represents the red color ball, 2 represents the white color ball and 3 represents the blue color ball.

Analysis

Running Time : We traverse the array only once. Hence the running time would be of the order O(N).

Auxiliary Space
As we can see there is not much of extra space required, we only used few pointers. So the space requirement is constant.

Don’t forget to subscribe to TechieMe to get updates on latest posts.

• Anju

great pictorial description! thanks makes it very easy to understand

• Thank you for the much needed appreciation. I really appreciate that.

• Ashish Karn

Great explanation ðŸ˜€

• Thank you for the appreciation. You can always help by following and spreading the word ðŸ™‚

• dogbert82

Thanks for taking your time to explain this! Great diagrams and explanation! You cannot find a better explanation than this!