Sort Colors

Problem Given an array whose values are 0 (red), 1 (white), 2 (blue), sort it in place so equal colors are adjacent in red→white→blue order — one pass, no library sort.

Input / Output

• Input: int array nums over {0,1,2}. Output: nums sorted in place.

Constraints

• n up to 3*10^5; the target is one pass with O(1) space; counting sort (two passes) is the fallback.

Example

• [2,0,2,1,1,0] → [0,0,1,1,2,2]

Expected approach

• Dutch national flag: pointers low, mid, high. While mid <= high: 0 → swap(low++, mid++); 1 → mid++; 2 → swap(mid, high--) without advancing mid (incoming value unexamined). Invariants: [0,low) zeros, [low,mid) ones, (high, n) twos. O(n)/O(1). Explaining why mid doesn't advance on the high-swap is the standard probe.