In this article, we have explored the Dutch National Flag Problem which is a standard Algorithmic Problem proposed by Edsger Dijkstra. It is solved efficiently using Three Way Partitioning technique.

Table of contents:

• Introduction
• The Problem
• Solution
• Psuedocode
• Three way Partition
• Time and Space Complexity

Pre-requisite:

• Three Way Partitioning

Introduction

This problem of The Dutch National Flag was proposed in the book "A Discipline of Programming Prentice-Hall" which was written by Edsger Dijkstra.

The problem is about grouping three kinds of elements in three separate groups which were mixed.

Dijkstra named this problem the "Dutch National Flag Problem" by looking at the problem as if we have three colors of pebbles red, white, and blue which are mixed together, and we have to arrange them all together in three different groups of red, white, and blue like the "Dutch National Flag"

The Problem

We have three colors of stone red, white, and blue, we need to arrange these stones in one order such that every same color of stones forms one group.
Dijkstra also mentions three conditions that the Algorithm should follow,

1. The given array can have three colors or two colors or one color of stones or No stones, our program should be able to handle these situations as well.
2. We don't have lots of memory to create any form of the new array, the program should only introduce some fixed length of variables.
   So, in short, the Space complexity should not increase O(1).
3. If possible The program should only look at one stone for once.

Note: For colors, we will be taking numbers such as 1, 2 and 3

Solution

The solution is to divide the whole given array into four sections,

1. The first section is the red section which contains arranged red stones.
2. The second section is the white section which contains arranged white stones.
3. The third section is for all colors mixed, (yet not arranged).
4. The last one is the blue section which only contains blue stones.

Using this approach we will take r, w, and b, indexes for red, white, and blue colors respectively.

1. r stores the index value of the position where the red color ends.
2. same as r, w stores the index value of position where the white color ends.
3. whereas b stores the index value of position where blue color starts.

Note: r, w, and b are exclusive pointers. So, they do not include the value the group they refer to.

Now, after setting the r, w, and b in this manner we will continuously check the value at w and perform actions according to the value.
So, if the found value is,

1. Red
   On red we will swap the value of r and w, And then increment the indexes of r and w.
   So, the idea here is, if we found a red stone we will put a red stone at end of the Red Section and the value that will be available at r (which will be white) will come at the end of the White Section.
   Here, incrementing the indexes r and w will again put the array in the four sections as before.

2. White
   If we get white stone while checking value at w, which should have the index value of the end of the White Section, So, we will just increment the index value w.

3. Blue
   On blue, we will perform a swap between w and b, now since doing this will put the blue at the start of the Blue Section and put whatever unknown there was at b in the w, because of this w can have arbitrarily any value.
   Therefore, we will decrement the b (to put the pointer again at the start of the Blue Section).

Psuedocode

arr := "Provided with elements 1, 2, and 3"
r = 0
w = 0
b = length(arr) - 1

while ( w <= b ):
    if arr(w) == 1:
        swap(w, r)
        w++
        r++
   else if arr(w) == 3:
       swap(w, b)
       b--
   else if arr(w) == 2:
       w++

Three Way Partition

As you might notice that the whole array is now divided into three sections, the blue one containing only 1's and the white one containing only 2's and the blue one containing only 3's.

If we make a few changes in the above Algorithm, then we can create an Algorithm called the Three Way Partition Algorithm, which takes two points and an array and creates a resulting array in which,

1. The First partition contains only values that are less than the first point.
2. The Mid partition contains only values, those are lying between the first and second points.
3. The third partition contains all values, which are greater than the third point.

If you want to try this, then assume two points,
let's say p1 and p2,

• Now, instead of checking if we have a red element on w, check if the value of the element is less than the p1.
• And instead of checking if the element is blue on the w pointer, check if the value of the element is greater than the p2.

Time Complexity: O(N)

We can see that in the whole Algorithm theirs only one loop which executes until the w pointer passes the b pointer, since the w pointer increases in every iteration except whenever we find the element which should go to Blue Section, therefore we can that we're going through the whole, array for once, And since, the array contains N number of elements.

Therefore,

Time Complexity: O(N)

Space Complexity: O(1)

So, as per the conditions, we only have some limited memory to use other than the provided N number of elements, and we're creating only r, w, and b pointers, which are going to remain of the same size throughout the whole iteration, therefore:

Space Complexity: O(1)

With this article at OpenGenus, you must have the complete idea of Dutch National Flag Problem.