Dutch National Flag

Edsger Dijkstra coined the Dutch National Flag problem: given an array containing only 0s, 1s, and 2s (the three colours of the Dutch flag), sort it in a single pass without counting. The trick is maintaining three invariants simultaneously with three pointers.

Pointer Invariants

At any point during the scan:

• Everything before low is 0
• Everything from low to mid - 1 is 1
• Everything from mid to high is unseen (the “unknown” zone)
• Everything after high is 2

The algorithm runs mid through the unknown zone, swapping elements into the correct region and adjusting the boundary pointers.

Implementation

function sortColors(nums) {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      // Swap into the 0-region
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      // Already in the 1-region, just advance
      mid++;
    } else {
      // Swap into the 2-region; don't advance mid — we haven't seen nums[mid] yet
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

const arr = [2, 0, 2, 1, 1, 0];
sortColors(arr);
console.log(arr); // [0, 0, 1, 1, 2, 2]

Walked Example

Starting with [2, 0, 2, 1, 1, 0], low=0, mid=0, high=5:

Result: [0, 0, 1, 1, 2, 2]

Why Not Just Count?

Counting 0s, 1s, and 2s and overwriting takes two passes. The Dutch flag does it in one and is useful when the values cannot be re-enumerated (e.g., the elements are objects with a colour property rather than integers).

Complexity

Up Next

With array patterns covered, we move to strings — starting with what a JavaScript string actually is under the hood.