Dutch National Flag — Three-Way Partition

What does it solve?

Given an array containing only 0s, 1s, and 2s, sort it in-place in a single pass — without counting or using extra space.

Named after Edsger Dijkstra's thought experiment: arrange red, white, and blue segments of a flag. Three pointers divide the array into four live zones.

The core idea

// lo=left of 0s, mid=scanner, hi=right of 2s
while mid <= hi:
  if arr[mid] == 0: swap(lo,mid); lo++; mid++
  elif arr[mid] == 1: mid++
  else: swap(mid,hi); hi--

▶ Visualiser

0s region (sorted)

1s region (sorted)

2s region (sorted)

Unknown (unsorted)

Step — of —

lo pointer

—

left boundary

mid pointer

—

scanner

hi pointer

—

right boundary

Action

—

Select an example and press Play to start.

✓ Sorted

Speed Medium

Step-by-step table

#	lo	mid	hi	arr[mid]	Action	Array state

C++ implementation

dutch_national_flag.cpp

#include <bits/stdc++.h>
using namespace std;

void sortColors(vector<int>& nums) {
    int lo = 0, mid = 0, hi = nums.size() - 1;

    while (mid <= hi) {
        if (nums[mid] == 0) {
            swap(nums[lo], nums[mid]); // push 0 to left zone
            lo++; mid++;
        } else if (nums[mid] == 1) {
            mid++;                     // 1 is already in place
        } else {
            swap(nums[mid], nums[hi]); // push 2 to right zone
            hi--;                      // don't advance mid — re-examine
        }
    }
}

int main() {
    vector<int> nums = {2, 0, 2, 1, 1, 0};
    sortColors(nums);
    // nums is now [0, 0, 1, 1, 2, 2]
    return 0;
}

Complexity

Time complexity

O(n)

Each element is visited at most once. The mid pointer only moves forward; hi only moves backward — so the loop terminates in exactly n iterations.

Space complexity

O(1)

Three integer pointers (lo, mid, hi) — no auxiliary array. Sorting happens entirely in-place via element swaps.

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars