Dutch National Flag Problem

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

  1. Start with three pointers : reader, low and high.
  2. reader and low are initialized as 0 and high is initialized as last element of array as size-1.
  3. reader will be used to scan the array while low and high will be used to swap elements to their desired positions.
  4. Starting with current position of reader, follow below steps, keep in mind we need 0 at start of array
    1. If element at index reader is 0, swap element at reader with element at low and increment low and reader by 1.
    2. If element at reader is 1, do not swap and increment reader by 1.
    3. If element at reader is 2, swap element at reader with element at high and decrease high by 1

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.

dutch national flag problem

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

dutch national flag algorithm

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

dutch national flag problem

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

dutch national flag problem

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.

Dutch national flag algorithm explanation

Element at reader is 1, just increment reader.

dutch national flag problem

Element at reader is 1, just increment reader.

Dutch national flag algorithm explanation

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

dutch national flag problem

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

Dutch national flag algorithm explanation

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

dutch national flag problem

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.