# DUTCH NATIONAL FLAG (DNF)

The Dutch national flagproblem is one of the most popular programming problems proposed by Edsger Dijkstra.Yes Dijkstra is everywhere !

The flag of the Netherlands consists of three colors: white, red, and blue. The task is to randomly arrange balls of white, red, and blue such that balls of the same color are placed together

We can have a variety of problems based on this concept. Let us take two very famous problems which can be solved using this approach

Although we won’t be using colors, the premise of the challenge is to develop a sorting algorithm that performs some form of separations of three kinds of elements.

# Sort an array of 0’s, 1’s, and 2’s

- Brute force is to sort the array O(NlogN) we can do a lot better than that
- Efficient approach is to just count the no of 1’s, 2’s and 3’s in one for loop and then put the values in the array in another loop O(N) time but it requires 2 traversals
- Can we do this in just 1 traversal ? Yes !! DUTCH NATIONAL FLAG !!

# ALGORITHM -

- Take three-pointers, namely — low, mid, high.
- We use low and mid pointers at the start, and the high pointer will point at the end of the given array.
- low is for 0’s, mid is for 1’s and high is for 2’s (you would have figured this out already…I hope so xD)

- Index
`0`

to`low`

- this is the "bottom group"**(O’s)** - Index
`low`

to`mid`

- this is the "middle group"**(1’s)** - Index
`mid`

to`high`

- this is the "top group"**(2’s)**

# CASES :

- If array [mid] =0, then swap array [mid] with array [low] and increment both pointers once.
- If array [mid] = 1, then no swapping is required. Increment mid pointer once.
- If array [mid] = 2, then we swap array [mid] with array [high] and decrement the high pointer once.

## Time to get our hands dirty !!

C++ code snippet

int n = arr.size();

int low = 0, mid =0,high = n - 1;while (mid <= hi) {

switch (a[mid]) {

// If the element is 0

case 0:

swap(a[low++], a[mid++]);

break;

// If the element is 1 .

case 1:

mid++;

break;

// If the element is 2

case 2:

swap(a[mid], a[high--]);

break;

}

}

}

Python code snipet:

`low = 0 `

high = arr_size - 1

mid = 0

while mid <= high:

if arr[mid] == 0:

arr[low],arr[mid] = arr[mid],arr[low]

low = low + 1

mid = mid + 1

elif arr[mid] == 1:

mid = mid + 1

else:

arr[mid],arr[high] = arr[high],arr[mid]

high = high - 1

return arr

**Congrats** !! You know how to solve 1 problem on DNF !! Wanna practice one more problem ?

Let us take another problem on DNF ( I know you are loving this concept !)

## Three way partitioning of an array around a given range

Problem statement :

Given an array and a range [**lowVal**, **highVal**], partition the array around the range such that array is divided in three parts.

1) All elements smaller than **lowVal** come first.

2) All elements in range **lowVal** to **highVVal** come next.

3) All elements greater than **highVVal** appear in the end.

The individual elements of three sets can appear in any order.

Eg

Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}

lowVal= 14,highVal= 20Output: arr[] = {1, 5, 4, 2, 1, 3,14, 20,20, 98, 87, 32, 54}

## Your thought process

*You brain now must be thinking about how this is a DNF problem …well the problem asks us to divide the array into 3 (YES 3 !!) partitions and its related to order(sorting) so it can be solved with DNF !*

Worst appraoch : use sorting (NlogN)

So how to apply DNF here ?

The **algorithm** will be as follows:

Try to code this by yourself and then come to this solution

C++ code snippet

vector<int> threeWayPartition(vector<int> &arr, int a, int b)

{

int n = arr.size();

int low = 0, high = n - 1;

int index = 0; //Traverse all elements of array

while (index <= high)

{ //Place elements less than a to front

if (arr[index] < a)

{

swap(arr[index], arr[low]);

index++;

low++;

} //Place elements greater than b to back

else if (arr[index] > b)

{

swap(arr[index], arr[high]);

high--;

} else

index++;

}return arr;

}

YIPPEE !! YOU DID IT !