Dutch National Flag Problem
Get this book > Problems on Array: For Interviews and Competitive Programming
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:
Prerequisite:
Introduction
This problem of The Dutch National Flag was proposed in the book "A Discipline of Programming PrenticeHall" 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,
 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
Solution
The solution is to divide the whole given array into four sections,
 The first section is the
red section
which contains arranged red stones.  The second section is the
white section
which contains arranged white stones.  The third section is for all colors mixed, (yet not arranged).
 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.
r
stores the index value of the position where the red color ends. same as
r
,w
stores the index value of position where the white color ends.  whereas
b
stores the index value of position where blue color starts.
Note:
r
,w
, andb
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,

Red
On red we willswap
the value ofr
andw
, And then increment the indexes ofr
andw
.
So, the idea here is, if we found ared stone
we will put ared stone
at end of theRed Section
and the value that will be available atr
(which will be white) will come at the end of theWhite Section
.
Here, incrementing the indexesr
andw
will again put the array in the four sections as before. 
White
If we getwhite stone
while checking value atw
, which should have the index value of the end of theWhite Section
, So, we will just increment the index valuew
. 
Blue
On blue, we will perform a swap betweenw
andb
, now since doing this will put theblue
at the start of theBlue Section
and put whateverunknown
there was atb
in thew
, because of thisw
can have arbitrarily any value.
Therefore, we will decrement theb
(to put the pointer again at the start of theBlue 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,
 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,
let's say p1
and p2
,
 Now, instead of checking if we have a
red
element onw
, check if the value of the element isless than
thep1
.  And instead of checking if the element is
blue
on thew
pointer, check if the value of the element isgreater than
thep2
.
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.