Sort Colors
Sort Colors: sort an array of 0s, 1s, and 2s in place in a single pass (the Dutch National Flag problem).
- n == nums.length
- 1 <= n <= 300
- nums[i] is either 0, 1, or 2.
Intuition
Sort colors sorts an array containing only 0s, 1s, and 2s, in place and in a single pass. Counting each value and overwriting works in two passes; the one-pass solution is the Dutch National Flag algorithm.
With only three distinct values, the array can be partitioned into three regions maintained simultaneously:
- Three pointers divide the array — everything before low is 0, everything after high is 2, and the region between low and mid is 1.
mid scans forward and each value it meets is handled by one rule. A 0 swaps to the low boundary, advancing both low and mid. A 1 is already correct, so only mid advances. A 2 swaps to the high boundary and high retreats — and crucially mid does not move.
That asymmetry is the crux. After swapping with high, the value received came from unexamined territory and must be inspected. Advancing mid skips it, leaving 2s stranded in the middle. Swapping with low, by contrast, brings back an already-classified value, so advancing is safe.
The loop runs while mid <= high, inclusive. Using < leaves the final element unclassified.
Each element is examined at most twice — once by mid and possibly once after a swap — so the pass is genuinely linear despite the swapping.
The counting-sort approach is simpler and often preferable in practice: tally the three values, then overwrite. Two passes, same O(n), and much harder to get wrong. The problem specifically asks for one pass, which is why the three-pointer version is the expected answer.
One pass gives O(n) time and O(1) space.
The Dutch national flag partition: three pointers carve the array into [0s | 1s | unknown | 2s]. The invariant is that everything left of low is 0, everything between low and mid is 1, and everything right of high is 2. Any "sort three distinct values in one pass" question is this pattern.
Approach
Before reading on: counting the three values and rewriting works but touches the array twice. Ask what three pointers would need to mean for one pass to suffice — and which region each pointer bounds.
Note the three-value constraint
Only 0s, 1s, and 2s appear, so the array partitions into three regions rather than needing a general sort.
Maintain three pointers
Everything before low is 0, everything after high is 2, and mid scans the unclassified middle. The invariant holds throughout.
Swap zeros to the front
On a 0, swap with low and advance both low and mid — the value received is already classified, so moving on is safe.
Leave ones in place
A 1 belongs where it is, so only mid advances. No swap is needed.
Do not advance mid after a 2
Swapping with high brings back an unexamined value that must be inspected. Advancing mid skips it and strands 2s in the middle — the defining bug.
Use an inclusive loop bound
Run while mid <= high. Using < leaves the final element unclassified.
Cost of the approach
Each element is examined at most twice, giving O(n) time and O(1) space in a single pass, as the problem requires.
Solution & live demo
Common pitfalls
Advancing mid after swapping with high
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
mid += 1else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1The value swapped in from high has never been examined — it could be a 0 or a 2. Advancing mid skips over it unclassified. Swapping with low is different: that value was already known to be a 1, so mid can safely move.
Looping while mid < high
while mid < high:
while mid <= high:
When mid == high there is still one unclassified element sitting at that index. Stopping early leaves it in place, so a final stray 0 or 2 stays unsorted.
Counting occurrences and rewriting
c = [nums.count(0), nums.count(1), nums.count(2)] nums[:] = [0]*c[0] + [1]*c[1] + [2]*c[2]
low, mid, high = 0, 0, len(nums) - 1
Counting sort is correct but makes two passes, and the problem explicitly asks for a one-pass in-place solution. The three-pointer partition does it in a single sweep.
Edge cases
0 swaps with itself, 1 is skipped, 2 swaps with itself — order is preserved.
All-0 advances both low and mid; all-2 shrinks high; all-1 just advances mid. Each terminates cleanly.
Because mid does not advance on a 2-swap, the freshly swapped value is re-examined, never skipped.