Let's talk about this very intersting algorithm by Edsger Dijkstra, a Dutch Computer Scientist!

But before getting into it let's see a problem that was asked in Microsoft interview

Question for you 😼

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

After reading the problem you might think 🤔 is that even a Question to be asked in Microsoft? But to your surprise let me tell you it's a Medium level Leetcode Question.

The most probable solution that you might have thought of would be : sort the Array using any sorting techniques. SIMPLE

I thought the same but there's more to it. Let me tell you

Whenever we write a solution for a problem, the interviewer is looking for the most optimal solution one can think of. Optimal here would be a solution with a better Time Complexity.

Approach 1️⃣

The brute force solution (a simple general solution ) to solve this question would be Sorting the array using any sorting algorithm lets say we use Merge Sort here.

Time complexity for the brute force solution would be O(nlogn) which is good but we need a better optimal solution.

Approach 2️⃣

The second approach to this question can be Counting Sort.

We can linearly traverse through the array and count the number of 0's (here you'll get 2) then count the number of 1's ( which is also 2 ) and then you'll count the number of 2's ( also 2 )

Now you can run a loop for 2 times and put two 0's in the first two place then run a loop for another 2 times and put two 1's in the next two places and then put two 2's in the next two places.

The array is sorted!

Talking about the Time complexity for the Counting Sort Approach is:

O(n) (for traversing through the Array)+O(n) (for putting the elements in the array) = O(2n).

Approach 3️⃣ : Dutch National flag Algorithm

Here comes the Dutch National flag Algorithm for the Optimal solution of this problem.

Aim of this algorithm :

elements between [0 - (low-1)] is 0

elements between [low - (mid-1)] is 1

elements between [(high+1) - nums.length] is 2.

Focus on what we are doing for now, otherwise you'll get confused. further in the blog we explained how it's working.🟩

You'll need three pointers here int low; int mid; int high

The low and the mid pointer will be pointing at 0 and the high as you might have guessed would be pointing at the last element.

In this algorithm we are concerned about which element is at nums[mid]

Everytime nums[mid] = 0, swap nums[mid] and nums[low] and increment by mid and low by 1.

when nums[mid] = 1, just increment mid by 1.

when nums[mid] = 2, swap nums[mid] and nums[high] and decrement high by 1.

How's it's working

Initially the array is like this with the pointers low, mid and high pointing to the start and end respectively.

for the last two pass swapping nums[mid] and nums[low] when nums[mid] = 0, doesn't makes any changes to the array, just the pointers get incremented by 1.

Code for Dutch-National Flag

import java.util.Arrays;
public class lc75_DNF {
    public static void main(String[] args) {
        int[] arr= {2,0,2,1,1,0};
        sortColors(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sortColors(int[] nums) {
        int low= 0;
        int mid= 0;
        int high = nums.length - 1;
        while(mid <=high){
            switch (nums[mid]) {
                case 0:
                    swap(nums, low, mid);
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    swap(nums, mid, high);
                    high--;
                    break;
            }
        }
    }

    static void swap(int[] arr, int j, int i) {
        int temp = arr[j];
        arr[j] =arr[i];
        arr[i] = temp;
    }
}

The time Complexity for the Dutch-National Flag Algorithm is O(n) and the Space Complexity is O(1).

better than the previous two approaches!

Questions you might have

1. Does it work on only three numbers?
   Ans: Yes it works on only three numbers

2. Why is it called the Dutch-National Flag Problem
   Ans: The Dutch National Flag has three colors Red, White and Blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

That's pretty much it guys! Thank you for reading till the end,I hope it helped for any doubts regarding any steps comment below I'll answer it ! 🙏🏽

Let's connect on Twitter 🐦

Twitter-Souvik Raj Singh