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.
**mid** pointer passes the **high** pointer.
## Example

## Code

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

(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 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])

mrdaniel
published this on 11/24/15 **|**

5

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); }

sunyikang

commented on 10/27/16

Log in to submit a comment.