Sort Colors (Dutch National Flag)
Module 10 · Two Pointers
Problem
An array contains only 0s, 1s, and 2s (red/white/blue). Sort it in place, in one pass, without the library sort.
Examples
Example 1
Input
[2,0,2,1,1,0]Output[0,0,1,1,2,2]Example 2
Input
[2,0,1]Output[0,1,2]Example 3
Input
[0]Output[0]Constraints
1 ≤ n ≤ 300 · values ∈ {0,1,2} · follow-up: one pass, O(1) space.
Attempt it first
The partition lesson handed you the three-zone picture and derived the asymmetric mid rule. Reconstruct the algorithm from the picture — drawing the four regions and asking "what restores the invariant?" for each of the three possible values at mid. If you get stuck on whether mid advances, you're at the exact spot the lesson said you would be; go back to the regions, not to trial and error.