Dutch Flag Problem

Problem Definition – Dutch Flag Problem

The dutch flag looks like the below image.

dutchflag

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.

DUTCHFLAG

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:

step1_dfp

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:

step2_dfp

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:

step3_dfp

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:

step4_dfp

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:

step5_dfp

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:

step6_dfp

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:

step7_dfp

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:

step8_dfp

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.

step9_dfp

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.

Source Code – Dutch Flag Problem

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!