You're given an array nums of n items, each painted red, white, or blue — encoded as 0, 1, and 2. Rearrange them in-place so all the reds come first, then the whites, then the blues.
In other words: sort an array that contains only the values 0, 1, and 2, so the result is non-decreasing. The catch — you may not call the language's built-in sort. The array must be reordered inside itself, and the same array is returned.
The real challenge is the follow-up: can you do it in one pass using only constant extra space?
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Two reds, two whites, two blues — grouped in color order.
Input: nums = [2,0,1] Output: [0,1,2] One of each, laid out red → white → blue.
- n == nums.length - 1 <= n <= 300 - nums[i] is either 0, 1, or 2
Sort Colors is Edsger Dijkstra's Dutch National Flag problem, and it's the cleanest place to learn a three-way partition. The insight is that with only three possible values you don't need a comparison sort at all — and the one-pass version teaches a pointer dance (why one pointer doesn't advance) that trips up almost everyone the first time.
O(n).< 1, = 1, and > 1 regions in a single sweep.Given nums containing only 0, 1, 2, sort it in place (no library sort) so all 0s come first, then 1s, then 2s.
Worked example — nums = [2, 0, 2, 1, 1, 0]
low, mid at 0; high at 5 mid=2 → swap with high, high-- [0,0,2,1,1,2] (mid stays!) mid=0 → swap with low, low++, mid++ [0,0,2,1,1,2] mid=0 → swap with low, low++, mid++ [0,0,2,1,1,2] mid=2 → swap with high, high-- [0,0,1,1,2,2] (mid stays!) mid=1 → mid++ ; mid=1 → mid++ → done: [0,0,1,1,2,2] ✓
“Are the only values 0, 1, and 2?”
Yes — that's what lets you beat a general O(n log n) sort with a linear partition.
“Am I allowed to call the library sort?”
No — the exercise is precisely to exploit the three-value structure by hand.
“What about all-same or already-sorted arrays?”
The pointers simply march through; the three-way partition handles them without special cases.
“In place, returning the same array?”
Yes — mutate nums directly.
“Is one pass with O(1) space required?”
It's the real target (the follow-up). Counting sort is a clean O(n) two-pass warm-up; Dutch flag does it in one.
A couple of questions.
The array holds only 0, 1, and 2, and I can't use the built-in sort?
Should I aim for one pass with O(1) extra space?
Then I'll use Dijkstra's Dutch-flag three-pointer partition.
Sorting is O(n log n) in general, but with a fixed tiny alphabet you can count instead of compare. Tally the 0s, 1s, 2s and rewrite — O(n), two passes. That alone beats a library sort.
low marks the end of the settled 0s, high the start of the settled 2s, and mid scans the unknown middle. On a 0, swap into low and advance both low and mid; on a 1, just advance mid; on a 2, swap into high and shrink high. Continue while mid <= high.
When you swap a 2 to the back, the value pulled in from high is unexamined — it could be 0, 1, or 2. So mid has to re-inspect it and must stay put. After swapping a 0, the incoming value came from below mid and is already known-sorted, so mid can safely advance. That asymmetry is the whole subtlety.
| Counting sort | Dutch flag | |
|---|---|---|
| Idea | Tally counts, rewrite in order | Three-pointer partition |
| Time | O(n) | O(n) |
| Space | O(1) | O(1) |
| Passes | 2 | 1 |
The full code for both is in the Approaches selector below.
Key takeaway
For a fixed tiny alphabet, skip comparison sorting: Dijkstra's Dutch National Flag partitions 0/1/2 in a single O(n), O(1) pass with three pointers — swap 0s to low, 2s to high, leave 1s. The one gotcha: after swapping in from high, don't advance mid, because that value is still unexamined. It's the same three-way partition that hardens quicksort against duplicate keys.