Dutch National Flag problem is a very important and concept building problem. The question in itself very intuitive in nature and helps in building a strong problem solving approach. In this article, we will go through three phases:

1. Problem-statement
2. Intuition
3. Working code

Lets look at the problem statement now:

Given an array consisting of only 0s, 1s, and 2s. The task is to sort the given array. The solution should put all 0s first, then all 1s and all 2s in last.

// Sort the given array

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

The question requires us to simply sort the array which can be done in many ways. We can simply use the in-built sort function of the programming language that we are working with. We can also go for any of the sorting algorithms that we normally use, like insertion sort, bubble sort, merge sort etc. But will this be the most optimal solution for this particular problem?

The answer to that is No, because here we know what elements we are dealing with. We know that the array can only have 0s, 1s and 2s. This brings us to the intuition of this question which is actually very interesting.

Let’s consider the given array as a container which can be divided in three parts. If we have to sort the array, the first or leftmost part should contain all the 0s, the middle part should contain all the 1s and the last or the rightmost part will contain all the 2s. Now we simply have to move through the array, going through each element and put them in their actual partition. Now how do we keep track of these partitions?

To solve this problem, we will make use of three pointers. We will need three variables for this:

i. ‘left’ pointer

ii. ‘right’ pointer

iii. ‘mid’ pointer

For now, just think of these pointers as indicators of the three partitions that we are going to make in this array. These are not physical partitions, rather these are logical partitions and you need to visualise them. Now, lets see where each of these pointers lie. So, if we look at it, our left pointer should start at the 0th index of the array, because that marks the start of our first partition. Our mid pointer should also start at the 0th index and I’ll tell you why. As I stated earlier, we will need to traverse the array to check each of the element to know which partition it belongs . The mid pointer will take care of this requirement. Our right pointer will point to the extreme right i.e. the last index of the array as this will take care of our last partition.

Now, if we look carefully, our pointers are placed at places where we need to place the current element that we are looking at based on its value. This brings us to three scenarios:

i. Current element is a 0. In this case, since we are traversing using the mid pointer and our mid pointer should always be pointing to 1s (because of the pointers representing partitions). So in this case, we need to move the encountered 0 to its partition which is represented by left pointer. So we just swap the elements of mid and left pointer and move both the pointers forward. Why? Because now since the the place left pointer was pointing to (which was for 0s) is now occupied by a 0. So we keep a track of the next place that we need to fill.

ii. Current element is a 1. In this case, its very simple. Since mid pointer was supposed to point to 1s only, we will simply move the mid pointer forward.

iii. Current element is a 2. In this case, we need to move the encountered 2 to its partition which is represented by right pointer. So we just swap the elements of mid and right pointer and move right pointer in a backward direction. Why? Because now since the the place right pointer was pointing to (which was for 2s) is now occupied by a 2. So we keep a track of the next place that we need to fill.

I hope you got the intuition!! Now let’s look at the example we are going to use.

// placing pointer variables at their correct places
left = 0
mid = 0
right = arr.size()-1

// given array
arr = [1,2,0,1,0,2,2,1,0]

// When mid is at index 0, element is 1. Hence we simply move mid pointer
mid++

// When mid is at index 1, element is 2. Hence we swap mid and right pointer elements 
// and move the pointers accordingly

swap(arr[mid], arr[right])
right--
// arr = [1,0,0,1,0,2,2,1,2]

// When mid is at index 1, element is 0. Hence we swap mid and left pointer elements 
// and move the pointers accordingly

swap(arr[mid], arr[left])
left++; mid++
// arr = [0,1,0,1,0,2,2,1,2]

// When mid is at index 2, element is 0. Hence we swap mid and left pointer elements 
// and move the pointers accordingly

swap(arr[mid], arr[left])
left++; mid++
// arr = [0,0,1,1,0,2,2,1,2]

// When mid is at index 3, element is 1. Hence we simply move mid pointer

mid++
// arr = [0,0,1,1,0,2,2,1,2]

// When mid is at index 4, element is 0. Hence we swap mid and left pointer elements 
// and move the pointers accordingly

swap(arr[mid], arr[left])
left++; mid++
// arr = [0,0,0,1,1,2,2,1,2]

// When mid is at index 5, element is 2. Hence we swap mid and right pointer elements 
// and move the pointers accordingly

swap(arr[mid], arr[right])
right--
// arr = [0,0,0,1,1,2,2,1,2]

// When mid is at index 5, element is 2. Hence we swap mid and right pointer elements 
// and move the pointers accordingly

swap(arr[mid], arr[right])
right--
// arr = [0,0,0,1,1,1,2,2,2]

// When mid is at index 3, element is 1. Hence we simply move mid pointer

// Now since mid pointer goes beyond right pointer we are done with 
// our algorithm

Hence our array becomes, arr = [0,0,0,1,1,1,2,2,2]

Below is the working code for the same:

void sortArray(vector<int> nums) {
      int left= 0, mid = 0, right= nums.size()-1;
      while (mid <= right) {
          if (nums[mid] == 0) {
              swap(nums[mid], nums[left]);
              left++;
              mid++;
          }
          else if (nums[mid] == 1) {
              mid++;
          }
          else if (nums[mid] == 2) {
              swap(nums[mid], nums[right]);
              right--;
          }
      }
  }