Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Dutch National Flag Problem

Explore the Dutch National Flag problem solution by comparing brute force and optimized threeway partitioning methods. Understand how the efficient approach sorts the array in a single pass with O(n) time complexity, improving performance over naive selection sort. This lesson helps you grasp practical sorting techniques useful in coding interviews.

We'll cover the following...

Solution #1: Brute force

C++
#include "AuxiliaryFunctions.h"
void selectionSort(int arr[], int size) {
  int maxInd;
  for (int i = 0; i < size; i++) {
    maxInd = findMin(arr, i, size - 1); // findMin expects a start and end index so arrSize won't work
    swap(arr[i], arr[maxInd]);
  }
}
int main() {
  int size = 6;
  int arr[size] = {2, 0, 0, 1, 2, 1};
  selectionSort(arr, size);
  printArray(arr, size);
}

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 ...