Given an array of 0s, 1s, and 2s (red/white/blue), sort it in place in a single pass without a library sort or counting. e.g. [2,0,2,1,1,0] → [0,0,1,1,2,2].
The three-pointer Dutch National Flag partition — one pass, O(1) space — versus the easy but two-pass counting-sort answer.
The two-pass counting sort (tally 0/1/2, then overwrite) works, but the intended answer is Dijkstra's Dutch National Flag: partition into three regions in ONE pass with three pointers. Keep low (next slot for a 0), high (next slot for a 2), and a moving mid. When a[mid] is 0, swap it down to low and advance both low and mid; when it is 2, swap it up to high and shrink high only (do NOT advance mid, because the swapped-in value is still unexamined); when it is 1, just advance mid. Stop when mid passes high. The subtlety that trips people is exactly that 'don't advance mid after a swap-with-high'. Recognition signal: 'partition into three (or a few) categories around pivot values, in place, one pass' → three-pointer DNF. It generalises quicksort's partition to handle duplicate pivots (3-way quicksort). O(n) time, O(1) space.
In-place one-pass partition into three ordered groups (or 3-way quicksort partitioning around equal keys) → low/mid/high three-pointer sweep.
Time O(n) · Space O(1)