Interview Questions

Dutch national flag sorting problem
For this problem, your goal is to sort an array of 0, 1 and 2's but you must do this in place, in linear time and without any extra space (such as creating an extra array). This is called the Dutch national flag sorting problem. For example, if the input array is [2,0,0,1,2,1] then your program should output [0,0,1,1,2,2] and the algorithm should run in O(n) time.

## Algorithm

The solution to this algorithm will require 3 pointers to iterate throughout the array, swapping the necessary elements.
(1) Create a low pointer at the beginning of the array and a high pointer at the end of the array. (2) Create a mid pointer that starts at the beginning of the array and iterates through each element. (3) If the element at arr[mid] is a 2, then swap arr[mid] and arr[high] and decrease the high pointer by 1. (4) If the element at arr[mid] is a 0, then swap arr[mid] and arr[low] and increase the low and mid pointers by 1. (5) If the element at arr[mid] is a 1, don't swap anything and just increase the mid pointer by 1.
This algorithm stops once the mid pointer passes the high pointer.

## Code

```function swap(arr, i1, i2) {
var temp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = temp;
}

function dutchNatFlag(arr) {

var low = 0;
var mid = 0;
var high = arr.length - 1;

// one pass through the array swapping
// the necessary elements in place
while (mid <= high) {
if      (arr[mid] === 0) { swap(arr, low++, mid++); }
else if (arr[mid] === 2) { swap(arr, mid, high--); }
else if (arr[mid] === 1) { mid++; }
}

return arr;

}

dutchNatFlag([2,2,2,0,0,0,1,1]);
```
```def swap(arr, i1, i2):
temp = arr[i1]
arr[i1] = arr[i2]
arr[i2] = temp

def dutchNatFlag(arr):

low = 0
mid = 0
high = len(arr) - 1

# one pass through the array swapping
# the necessary elements in place
while mid <= high:
if arr[mid] == 0:
swap(arr, low, mid)
low += 1
mid += 1
elif arr[mid] == 2:
swap(arr, mid, high)
high -= 1
elif arr[mid] == 1:
mid += 1

return arr

print dutchNatFlag([2,2,2,0,0,0,1,1])
```

## Running time

This algorithm runs in O(n) time because it only passes through the array once swapping the necessary elements in place.

## Sources

http://www.glassdoor.com/Interview/Solve-Dutch-National-Flag-problem-QTN_309969.htm
mrdaniel published this on 11/24/15 |
• Provide another way using C#. ``` using System.Collections.Generic; static void Swap(int[] array, int x, int y) { int temp = array[x]; array[x] = array[y]; array[y] = temp; } static void DutchNationalFlag(ref int[] array) { int low = 0; int high = array.Length - 1; for (int i = 0; i <= high; i++) { if (array[i] == 0) Swap(array, low++, i--); if (array[i] == 2) Swap(array, i--, high--); } } public static void Main(string[] args) { int[] array2 = { 2, 2, 2, 0, 0, 0, 1, 1 }; DutchNationalFlag(ref array2); str = string.Join(",", array2); Console.WriteLine(str); } ```
• With O(n) time and O(1) memory you can as well just do bucket sort instead of using the more complicated pointers method. ```function dutchNatFlag(arr) { let counts = [0, 0, 0]; arr.forEach(x => counts[x]++); arr.forEach((x, i) => { if (counts[0]-- > 0) { arr[i] = 0; } else if (counts[1]-- > 0) { arr[i] = 1; } else { arr[i] = 2; } }); return arr; } dutchNatFlag([2,2,2,0,0,0,1,1]);```
• Another solution written in C++ which uses pretty much the same approach ```void mySwap(int * arr, int i, int j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } void DNF(int arrToSort [], int size) { int j=-1, i=0; while(i<size) { if(arrToSort[i]==0) { mySwap(arrToSort, i, j+1); j++; } i++; } j=size, i=size-1; while(i>=0) { if(arrToSort[i]==2) { mySwap(arrToSort, i, j-1); j--; } i--; } } ```