Medium · Dutch National Flag
Understand → Visualise → Practice.
When values come from exactly three categories, three pointers can place them without a general-purpose sort.
Keep 0s before `low`, 1s before `mid`, unknown values through `high`, and 2s after `high`.
Swap with low; advance low and mid.
It is already in the middle; advance mid.
Swap with high; reduce high but re-check mid.
O(n) time and O(1) extra space.
After swapping a 2 with `high`, do not advance `mid`; the incoming value is unclassified.
Read the full guides first: Sorting Algorithms and Their Trade-offs, Binary Search and Boundary Finding.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.