jsschools

Dutch National Flag Algorithm

Partitions an array of three distinct values (0, 1, 2) into three groups in a single pass using three pointers, achieving O(n) time and O(1) space.

Spec ↗

Syntax

dutchFlag(arr)

Parameters

NameTypeRequiredDescription
arr Array<0 | 1 | 2> Yes Mutable array containing only the values 0, 1, and 2 (or any three distinct comparable values).

Returns

void — Sorts the array in-place into [0s][1s][2s] order.

Examples

function dutchFlag(arr) {
  let lo = 0, mid = 0, hi = arr.length - 1;
  while (mid <= hi) {
    if (arr[mid] === 0) {
      [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
      lo++; mid++;
    } else if (arr[mid] === 1) {
      mid++;
    } else {
      [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
      hi--;
    }
  }
}

const arr = [2, 0, 2, 1, 1, 0];
dutchFlag(arr);
console.log(arr);
Output 
[ 0, 0, 1, 1, 2, 2 ]

// Generalised: partition around a pivot value (used in quick sort)
function dutchFlag(arr) {
  let lo=0,mid=0,hi=arr.length-1;
  while(mid<=hi){
    if(arr[mid]===0){[arr[lo],arr[mid]]=[arr[mid],arr[lo]];lo++;mid++;}
    else if(arr[mid]===1){mid++;}
    else{[arr[mid],arr[hi]]=[arr[hi],arr[mid]];hi--;}
  }
}

const single = [0];
dutchFlag(single);
console.log(single);

const allSame = [1, 1, 1];
dutchFlag(allSame);
console.log(allSame);
Output 
[ 0 ]
[ 1, 1, 1 ]

Notes

| Case | Time | Space | |---------|------|-------| | Best | O(n) | O(1) | | Average | O(n) | O(1) | | Worst | O(n) | O(1) | Proposed by Edsger Dijkstra, named after the Dutch flag (three coloured stripes). Three invariants maintained throughout: - `arr[0..lo-1]` = 0 (red) - `arr[lo..mid-1]` = 1 (white) - `arr[hi+1..n-1]` = 2 (blue) - `arr[mid..hi]` = unexplored The key subtlety: after swapping arr[mid] with arr[hi], we decrement hi but do NOT advance mid (the new arr[mid] is unknown). After swapping arr[mid] with arr[lo], both lo and mid advance because arr[lo] was 1 (from the invariant). This algorithm is used in the three-way partition of quick sort to efficiently handle arrays with many duplicate elements.

See also