Dutch National Flag Editorial

Practice Problem Link: Dutch National Flag | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Sort an array A where each of the elements belongs to the set: {0, 1, 2}.

Naive Approach

Just sort the array using any in-place sorting algorithm.

Analysis

• Time Complexity: O(n * logn)
• Space Complexity: O(1)

Implementation

C++

void sortTheArray (vector<int> &A) {
   sort(A.begin(), A.end());
}

Java

class Solution {
   void sortTheArray (int[] A) {
       Arrays.sort(A);
   }
}

Optimal Approach

The strategy is to exploit the fact that the array consists only 3 types of elements, {0, 1, 2}. Also, doing it in constant space hints at some swapping operation.

We will divide the array into 4 regions using 3 pointers, say low, mid, and high. The region [0, low - 1] will represent all zeroes, [low, mid - 1] will represent all ones, [mid, high - 1] will represent a yet unknown region, and [high, N] will represent the region with all twos.

The target is to shrink the size of the unknown region to zero when the algorithm converges. If the current element is 0, swap it into the low range, if the current element is 1, just move the mid pointer ahead, else swap the element into the high range. In this way, in every move, we reduce the size of the unknown region, and at the end, we get the sorted array.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

void sortTheArray (vector<int> &A) {
   int low = 0, mid = 0, high = (int)A.size() - 1;
   while(mid <= high) {
       if((A[mid]) == 0) {
           swap(A[low], A[mid]);
           low++;
           mid++;
       } else if(A[mid] == 1) {
           mid++;
       } else {
           swap(A[mid], A[high]);
           high--;
       }
   }
}

Java

class Solution {
   void swap(int[] A, int first, int second) {
       int temp = A[first];
       A[first] = A[second];
       A[second] = temp;
   }
   void sortTheArray (int[] A) {
       int low = 0, mid = 0, high = A.length - 1;
       while(mid <= high) {
           if((A[mid]) == 0) {
               swap(A, low, mid);
               low++;
               mid++;
           } else if(A[mid] == 1) {
               mid++;
           } else {
               swap(A, mid, high);
               high--;
           }
       }
   }
}