Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Dutch National Flag Problem

Explore the Dutch National Flag problem and learn an efficient three-way partitioning algorithm to sort arrays with three distinct values. This lesson helps you understand how to optimize sorting with O(n) time complexity using in-place swaps, contrasting it with a less efficient brute force approach.

We'll cover the following...

Solution #1: Brute force

Java
class DutchFlag {
 //sorting in ascending order using selection sort
 public static int[] selectionSort(int[] lst) {
  int size = lst.length;
  int index = 0;
  for (int i = 0; i < size; i++) {
   //finding the minimum value's index
   index = find_min(lst, i, size);
   //swapping it with current value
   int temp = lst[i];
   lst[i] = lst[index];
   lst[index] = temp;
  }
  return lst;
 }
 //function to find the index of the minimum value  
 public static int find_min(int[] lst, int start, int end) {
  int min = lst[start];
  int index = start;
  for (int i = start; i < end; i++) {
   if (lst[i] < min) {
    min = lst[i];
    index = i;
   }
  }
  return index;
 }
 //driver function
 public static void main(String args[]) {
  int[] arr = {
   2,
   0,
   0,
   1,
   2,
   1
  };
  System.out.println(Arrays.toString(selectionSort(arr)));
 }
}

We have used simple selection sort to rearrange the array in ascending order. This method is naive and does not cater to the fact that we have just three different digits for this problem.

Time complexity

The time complexity is also too high, i.e. O(n2 ...