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:
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"
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,
- 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.
- 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).
- 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
The solution is to divide the whole given array into four sections,
- The first section is the
red sectionwhich contains arranged red stones.
- The second section is the
white sectionwhich contains arranged white stones.
- The third section is for all colors mixed, (yet not arranged).
- The last one is the
blue sectionwhich only contains blue stones.
Using this approach we will take
b, indexes for red, white, and blue colors respectively.
rstores the index value of the position where the red color ends.
- same as
wstores the index value of position where the white color ends.
bstores the index value of position where blue color starts.
bare exclusive pointers. So, they do not include the value the group they refer to.
Now, after setting the
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,
On red we will
swapthe value of
w, And then increment the indexes of
So, the idea here is, if we found a
red stonewe will put a
red stoneat end of the
Red Sectionand the value that will be available at
r(which will be white) will come at the end of the
Here, incrementing the indexes
wwill again put the array in the four sections as before.
If we get
white stonewhile 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
On blue, we will perform a swap between
b, now since doing this will put the
blueat the start of the
Blue Sectionand put whatever
unknownthere was at
w, because of this
wcan have arbitrarily any value.
Therefore, we will decrement the
b(to put the pointer again at the start of the
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
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,
- The First partition contains only values that are less than the first point.
- The Mid partition contains only values, those are lying between the first and second points.
- The third partition contains all values, which are greater than the third point.
If you want to try this, then assume two points,
- Now, instead of checking if we have a
w, check if the value of the element is
- And instead of checking if the element is
wpointer, check if the value of the element is
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.
Time Complexity: O(N)
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
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.