Sort Colors (Dutch National Flag)
An array contains only the values 0, 1 and 2 representing three colors. Sort it in place in a single pass without using a library sort.
- 1 ≤ n ≤ 300
- nums[i] ∈ {0, 1, 2}
- Only three distinct values
- One pass, in place
- Three regions: zeros, ones, unknown, twos
When order gives you a way to decide which of two ends to move, you can replace an O(n^2) double loop by a single pass. Opposite-direction pointers exploit sortedness (move the side that must change); same-direction pointers maintain a "written so far" prefix for in-place compaction.
Maintain low, mid, high such that everything before low is 0, between low and mid is 1, after high is 2, and [mid, high] is unprocessed. Examine nums[mid]: if 0, swap with nums[low] and advance both; if 1, advance mid; if 2, swap with nums[high] and decrement high without advancing mid since the swapped-in value is unexamined. Stop when mid > high.
- Counting sort with two passes (count then overwrite) is simpler and also O(n); the three-pointer version is the single-pass answer interviewers expect.