DUTCH NATIONAL FLAG (DNF)

The Dutch national flag problem 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)

1. Index 0 to low - this is the "bottom group" (O’s)
2. Index low to mid - this is the "middle group" (1’s)
3. 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 = 20
Output: 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)

Nahhh !!

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 !

Go code all that you learned today xD

Thank You !