**Dutch National Flag Problem**

Given an array with 0s,1s and 2s, sort array in increasing order. Another way to phrase this problem is sort balls with three different colors : red, blue and white, where balls of each color are placed together. This is typically know as Dutch national flag problem and algorithm to solve it is called** Dutch national flag problem. **Example:

` A = [0,1,0,1,1,2,0,2,0,1]`

Output = [0,0,0,0,1,1,1,1,2,2]

` A = [R,B,B,W,B,R,W,B,B]`

Output = [R,R,W,W,B,B,B,B]

This problem can be asked as design question, as let’s say you have to design a robot. All this robot does is : it see three empty buckets and a bucket full of colored balls (red, blue and white). Design an instruction set for this robot that it fill each empty buckets with one color. It’s the same problem as Dutch National Flag problem.

## Count to sort an array of 0s,1s and 2s

We have already seen similar problem before as Segregate 0s and 1s in an array. We explored how to count elements and re-write them again on to array.

Let’s apply the same method for this problem. Take an array of three integers, index store corresponding count for that number. E.g `count[0]`

stores count of 0 and `count[1]`

stores count of 1. Scan through the array and count each element. At last, re-write those numbers back on to array starting from index 0, according to their count. For example, if there are 4 zeros, then starting from 0 index, write 4 zeros, followed by 1s and then by 2.

Complexity of counting method is `O(n)`

, notice that we scan array twice, first time for counts and second time for writing on array.

## Dutch national flag problem : algorithm

- Start with three pointers :
`reader`

,`low`

and`high`

. `reader`

and`low`

are initialized as`0`

and`high`

is initialized as last element of array as`size-1`

.- reader will be used to scan the array while low and high will be used to swap elements to their desired positions.
- Starting with current position of reader, follow below steps, keep in mind we need 0 at start of array
- If element at index
`reader`

is 0, swap element at`reader`

with element at`low`

and increment low and reader by 1. - If element at
`reader`

is 1, do not swap and increment reader by 1. - If element at
`reader`

is 2, swap element at`reader`

with element at`high`

and decrease high by 1

- If element at index

Actually, three pointers divide array into four parts. Red, white, unknown and Blue. Every element is taken from unknown part and put into its right place. So all three other parts expand while unknown part shrinks.

Let’s take an example and see how dutch national flag algorithm works.

First step, initialize reader, low and high.

Element at reader is 0, hence swap element at reader and low,also increment reader and low.

Follow the same step, check element at reader again, it’s 1, hence, just move reader by one.

Element at reader is now 2, swap element at reader with element at high and decrease high by 1.

Element at reader is 1, just increment reader.

Element at reader is now 2, swap element at reader with element at high and decrease high by 1.

Element at reader is 1, just increment reader.

Element at reader is 1, just increment reader.

Element at reader 0, hence swap element at reader and low,also increment reader and low.

Element at reader 0, hence swap element at reader and low,also increment reader and low.

Element at reader is now 2, swap element at reader with element at high and decrease high by 1.

Here, high becomes less than reader, we can stop as array is already sorted.

## Dutch national flag algorithm implementation

package com.company; /** * Created by sangar on 5.1.18. */ public class DutchNationalFlag { public static void swap(int[] input, int i, int j){ int temp = input[i]; input[i] = input[j]; input[j] = temp; } public static void dutchNationalFalgAlgorithm(int [] input){ //initialize all variables int reader = 0; int low = 0; int high = input.length - 1; while(reader <= high){ /* input always holds a permutation of the original data with input(0..(lo-1)) =0, input(lo..(reader-1))=1, input(reader..hi) is untouched, and input((hi+1)..(input.length-1)) = 2 */ if(input[reader] == 0){ /*When element at reader is 0, swap element at reader with element at index low and increment reader and low*/ swap(input, reader, low); reader++; low++; } else if(input[reader] == 1){ /* if element at reader is just increment reader by 1 */ reader++; } else if(input[reader] == 2){ /* If element at reader is 2, swap element at reader with element at high and decrease high by 1 */ swap(input, reader, high); high--; } else{ System.out.println("Bad input"); break; } } } public static void main(String[] args) { int[] input = {2,2,1,1,0,0,0,1,1,2}; dutchNationalFalgAlgorithm(input); for(int i=0; i<input.length; i++){ System.out.print(" " + input[i]); } } }Complexity of Dutch National Flag algorithm is

`O(n)`

, however, we scan the array only once.Please share if you have some suggestions or comments. Sharing is caring.