Dutch national flag problem

Learn how to implement an algorithm to solve the dutch national flag problem in ES6.

The problem is named after the three different colors(red, white, blue) used in flag of Netherlands. We are going to use an array containing 0s, 1s, 2s to represent the flag.

In technical term it is described as “Given an array consisting of 0s, 1s, and 2s, sort them in linear time and constant space”.

Example

Input:
[2, 0, 1, 0, 2]

Output:
//Sorted in ascending order
[0, 0, 1, 2, 2]

The catch for this problem is that we have to implement an algorithm which will be performing sorting in linear or O(n) time and using constant space O(1), But the good thing is there will be only 3 different types of elements in the array 0, 1, 2 or so.

Implementation

This implementation is variant of quicksort algorithm. We pick a pivot and compare it with other elements of the array and sort them.

• We are going to maintain three indexes low, mid, and high which will be used to arrange the array elements.
• Then we are going to loop till mid <= high.
• In each iteration we will check the value of the array element at mid index.
• If it is 0 the we will swap the array elements at index low++ and mid++.
• Else if it is 2 the we will swap the array elements at index mid++ and high--.
• Else just increase the mid++.

//Function to swap two elements
let swap = (arr, first, second) => {
  [arr[first], arr[second]] = [arr[second], arr[first]];
}

//Solution
let dutchNatFlag = (arr) => {
   let low = 0;
   let mid = 0;
   let high = arr.length - 1;
   
   //To sort in ascending order
   while (mid <= high) {
	if (arr[mid] === 0) { 
	    swap(arr, low++, mid++);
	} else if (arr[mid] === 2) {
	    swap(arr, mid, high--);
	} else if (arr[mid] === 1) {
	    mid++;
	}
   }

   return arr;
}

Input:
console.log(dutchNatFlag([2, 2, 2, 0, 0, 0, 1, 1]));
console.log(dutchNatFlag([0, 1, 2, 0, 1, 2]));

Output:
[0, 0, 0, 1, 1, 2, 2, 2]
[0, 0, 1, 1, 2, 2]

Update to this to sort in descending order

//To sort in descending order
   while (mid <= high) {
	if (arr[mid] === 2) { 
	    swap(arr, low++, mid++);
	} else if (arr[mid] === 0) {
	    swap(arr, mid, high--);
	} else if (arr[mid] === 1) {
	    mid++;
	}
   }

How it works

For example [0, 1, 2, 0, 1, 2]

• The loop begins with mid = 0 and high = arr.length - 1 = 5.
• Then we check the element at the mid.
• As arr[mid] = 0 we go inside the first condition and perform swap(arr, low++, mid++), Now low = 1 & mid = 1 and our array looks like [0, 1, 2, 0, 1, 2].
• As mid < high we again repeat the process until mid > high.

This is how array looks like after each swapping.

[0, 1, 2, 0, 1, 2]
[0, 1, 2, 0, 1, 2]
[0, 1, 1, 0, 2, 2]
[0, 0, 1, 1, 2, 2]

Time complexity: O(n).
Space complexity: O(1).

Time and Space complexity

• We are looping from 0 to n where n is the length of the array, so Time complexity is O(n).
• We are using constant space, so Space complexity is O(1).

---

Another approach to solve dutch national flag problem

There is another simple approach which we can use to solve the dutch national flag problem.

Implementation

• We will count all 0s, 1s, and 2s in the given array.
• Then we will update those in ascending or descending order in the array.

//Solution
let dutchNatFlag = (arr) => {
  let zeros = 0;
  let ones = 0;
  let twos = 0;
  
  //Count all the 0s, 1s, 2s
  for(let val of arr){
    if(val === 0){
      zeros++;
    }else if(val === 1){
      ones++;
    }else{
      twos++;
    }
  }
  
  //Update all the 0s
  for(let i = 0; i < zeros; i++){
    arr[i] = 0;
  }
  
  //Update all the 1s
  for(let i = zeros; i < (zeros + ones); i++){
    arr[i] = 1;
  }

  //Update all the 2s
  for(let i = zeros + ones; i < (zeros + ones + twos); i++){
    arr[i] = 2;
  }
	
  return arr;
}

Input:
console.log(dutchNatFlag([2, 2, 2, 0, 0, 0, 1, 1]));
console.log(dutchNatFlag([0, 1, 2, 0, 1, 2]));

Output:
[0, 0, 0, 1, 1, 2, 2, 2]
[0, 0, 1, 1, 2, 2]

If you want to sort in reverse order just swap the 0s and 2s order. This approach works fine but we have to use multiple loops.

Time complexity: O(n).
Space complexity: O(1).

Time and Space complexity

• We are looping through all the elements of array which will take O(n), then we are updating the count in the array which will take O(n), As all the loops are running one after another Time complexity is O(n) + O(n) + O(n) + O(n) = O(n).
• We are using constant space, so Space complexity is O(1).