Dutch national flag problem in Javascript

Dutch national flag problem and solution in Javascript

Problem statement: 

The Dutch national flag (DNF) problem is one of the most popular programming problems proposed by Edsger Dijkstra. 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.

Now, let's consider an array with 3 distinct values say 0, 1 and 2. We won't be using any sort method and we need to sort this array in 0(n).

Input Array : 

let arr = [0, 2, 1, 0, 1, 2, 0, 2];

Expected Output:

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

Solution Approach :

When we see expected output, we can clearly see that sorted array is divided into 3 sections having values 0 , 1 and 2. So, let's divide the array in 3 sections:

a) from 0th index to left boundary

b) from left boundary to right boundary

c) from right boundary to last index.

Now we will create 2 pointers : left (starting from 0) and right (starting from last index), these pointers will help us updating Zeroes and Twos.

And a 3rd pointer called current, which will help us traverse the array. 

Refer the below image for the input array with pointers.
 

Algorithm:

a) While current index is less than equal to right pointer, we will repeat below steps

b) If the value at current index is 2, we will swap it will the value present at right index and decrement right pointer.

c)  If the value at current index is 0, we will swap it will the value present at left index and increment left pointer and current pointer.

d) If the value at current index is 1, we will not do anything except current increment.

Let's write the code now:

let arr = [0, 2, 1, 0, 1, 2, 0, 2];

let n = arr.length;

let left = 0;

let right = n - 1;

let current = 0;

while (current <= right) {

  if (arr[current] == 2) {

    let temp = arr[right];

    arr[right] = arr[current];

    arr[current] = temp;

    // moving right boundary 1 index towards left

    right--;

  } else if (arr[current] == 0) {

    let temp = arr[left];

    arr[left] = arr[current];

    arr[current] = temp;

    // moving left boundary 1 index towards right

    left++;

    current++;

  } else {

    current++;

  }

}

console.log(arr);

Output:

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

 

Same problem is available on leetcode as well, give it a try: Sort Colors.