Run it
The three-way partition with its invariant asserted on every iteration, the buggy version that advances mid in both branches, and both checked against sorted() on random input.
Three pointers, three regions
The invariant is the whole algorithm, and it must be stated to reason about the code:
[0 … low−1] all 0s [low … mid−1] all 1s [mid … high] unknown [high+1 …] all 2s
Each branch preserves it:
A 0 is swapped to the front of the unknown region and both low and mid advance — the swapped-in element came from the 1s region, so it is a 1 and correctly placed.
A 1 is already in the right place; mid advances.
A 2 is swapped to the end and high retreats. mid must not advance, because the element swapped in came from the unknown region and has not been examined.
That last detail is the one bug this problem exists to catch. Advancing mid after a 2-swap skips an unexamined element, and the array comes out unsorted on inputs like [2, 0, 1].
Tracing it
[2, 0, 2, 1, 1, 0]:
| low | mid | high | nums[mid] | Action | Array |
|---|
| 0 | 0 | 5 | 2 | Swap with 5, high−− | [0,0,2,1,1,2] |
| 0 | 0 | 4 | 0 | Swap with 0 (self), both++ | [0,0,2,1,1,2] |
| 1 | 1 | 4 | 0 | Swap with 1 (self), both++ | [0,0,2,1,1,2] |
| 2 | 2 | 4 | 2 | Swap with 4, high−− | [0,0,1,1,2,2] |
| 2 | 2 | 3 | 1 | mid++ | [0,0,1,1,2,2] |
| 2 | 3 | 3 | 1 | mid++ | [0,0,1,1,2,2] |
| — | 4 | 3 | — | mid > high, stop | [0,0,1,1,2,2] |
Sorted, one pass, six iterations. Note the two self-swaps — harmless, and avoidable with a check that costs more than it saves.
The counting alternative
Count the 0s, 1s and 2s, then overwrite the array. Two passes, trivially correct, and usually the first answer. The question asks for one pass to rule it out — and because counting sort does not generalise to sorting objects by a three-way key, which the partition does.
The invariant
Everything before lo is 0. Everything from lo to mid is 1. Everything after hi is 2. Between mid and hi is unexamined. The loop restores that invariant on every step and stops when the unexamined region is empty.
Being able to state the invariant is most of the answer here. Writing the three branches from memory without it is how the mid bug appears.
The one asymmetry
After swapping a 0 into the low region, the value that came back is from the region already known to be 1s, so mid can safely advance. After swapping a 2 into the high region, the value that came back is from the unexamined region — so mid must stay and look at it.
Advancing in both cases is the classic bug: the array comes out almost sorted, with stray 2s left in the middle. It is exactly what the question is testing.
The loop condition
while mid <= high, not mid < high. With <, the final element in the unknown region is never examined, and an input ending in a misplaced value comes out wrong.
That is the second of the two off-by-one traps in this problem, and together with the "do not advance mid" rule they account for nearly every incorrect implementation.
| Bug | Symptom |
|---|
Advancing mid after a 2-swap | Unsorted output on [2,0,1] |
mid < high instead of <= | Last element unsorted |
Advancing low without mid | Infinite loop |
Swapping with low on a 2 | Corrupts the 0s region |
Where it comes from: quick sort
The Dutch national flag partition is the three-way partition used in quick sort with duplicate handling.
Standard two-way partitioning splits into "less than pivot" and "greater than pivot", and elements equal to the pivot end up scattered on one side. On an array with many duplicates, that means each partition removes only one element and quick sort degrades to O(n²).
Three-way partitioning places all elements equal to the pivot in the middle and recurses only on the outer two regions. An array of identical elements becomes the best case — one partition, O(n) total — instead of the worst.
That is the practical reason to know this pattern: arrays with few distinct values are common in real data (status flags, categories, boolean columns), and three-way partitioning is what handles them.
The variants
Two colours — move all zeros to the front. Two pointers, no middle region:
k colours — counting sort is the right answer once there are more than three values. Count, then overwrite. Two passes, O(n + k).
Partition around an arbitrary pivot — the same three regions with < pivot, == pivot, > pivot.
Sort by a predicate — move everything satisfying a condition to the front, which is the two-way case with a general test.
Wiggle sort and other rearrangement problems use related multi-pointer partitioning.
What it is testing
Do you find the one-pass solution? Counting is the obvious answer and it uses two passes; the constraint exists to push past it.
Do you state the invariant? Four regions with clear boundaries is what makes the code verifiable, and interviewers listen for it.
Do you handle the mid-pointer correctly? Not advancing after a 2-swap is the single most important detail.
Do you get the loop condition right? <=, not <.
Do you connect it to quick sort? Recognising it as three-way partitioning, and knowing why that matters for duplicates, is the answer that distinguishes understanding from memorisation.
Recap in one screen
- Three pointers maintain four regions: 0s, 1s, unknown, 2s — and the invariant is the algorithm.
- On a 0, swap forward and advance both
low and mid; on a 1, advance mid; on a 2, swap back and retreat high only. - Do not advance
mid after a 2-swap — the incoming element has not been examined. - The loop runs while
mid <= high, inclusive. - It is quick sort's three-way partition, which turns arrays of duplicates from the worst case into the best.