vizlearn

Sort an array of 0s, 1s and 2s

Interview QuestionsBy Updated

Three pointers carve the array into four regions: settled 0s, settled 1s, unexamined, and settled 2s. A 0 swaps down, a 2 swaps up, a 1 stays. One pass, O(1) space — and the one subtlety is that after swapping a 2 the middle pointer must not advance.

Overview

The problem

An array contains only 0s, 1s and 2s. Sort it in a single pass with O(1) extra space.

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

Two easy solutions are excluded by the constraints. Counting sort — count each value, then overwrite — is two passes. Any comparison sort is O(n log n) and does more than needed.

The single-pass answer is the Dutch national flag partition, named for the three-striped flag.

Lists & arraysCoding problemMedium

Step through it

What to watch

  • Four regions: settled 0s, settled 1s, unexamined, settled 2s.
  • After swapping a 2 down, mid stays — the incoming value is unseen.
  • The loop ends when mid passes hi, not the array end.

Say this out loud

"Dutch national flag. Three pointers - low, mid, high. 0 swaps to the low region and both advance, 2 swaps to the high region and only high moves, 1 just advances mid. One pass, O(1) space."

Sort an array of 0s, 1s and 2s

Sort an array containing only 0, 1 and 2 in a single pass, in place.

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.

1Python
Output
2Python
Output
3Python
Output

                

                

                    
Three pointers, three regions

                    
4Python
Output
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]:
lowmidhighnums[mid]ActionArray
0052Swap with 5, high−−[0,0,2,1,1,2]
0040Swap with 0 (self), both++[0,0,2,1,1,2]
1140Swap with 1 (self), both++[0,0,2,1,1,2]
2242Swap with 4, high−−[0,0,1,1,2,2]
2231mid++[0,0,1,1,2,2]
2331mid++[0,0,1,1,2,2]
—43—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.
BugSymptom
Advancing mid after a 2-swapUnsorted output on [2,0,1]
mid < high instead of <=Last element unsorted
Advancing low without midInfinite loop
Swapping with low on a 2Corrupts 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:
5Python
Output
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.

                

            


        

    



How the code works
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.
How the code works
  1. mid += 1 after a 0 swapSafe, because the value swapped back comes from the region already known to hold 1s. Nothing unexamined arrives at mid.
  2. no mid += 1 after a 2 swapThe value swapped back comes from the unexamined region, so it has to be looked at. Advancing here is the bug the second function demonstrates on real input.
  3. while mid <= hiThe loop ends when the unexamined region is empty, not at the end of the array — everything past hi is already settled.
  4. the three assert linesThe invariant, checked rather than described. Stating it is most of the answer to this question; writing the branches without it is how the bug appears.
Change one thing
  • Delete the asserts and add a fourth colour. The approach does not extend — three-way partitioning is specifically three-way.
  • Sort objects by a three-way key instead of raw integers. The partition still works; counting does not.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. After swapping a 2 from mid to the high region, why must mid stay?
  2. The regions maintained by the invariant are:
  3. Why is the counting approach not the accepted answer?





 Cheat sheet
Sort an array of 0s, 1s and 2s
Three pointers carve the array into four regions: settled 0s, settled 1s, unexamined, and settled 2s. A 0 swaps down, a 2 swaps up, a 1 stays. One pass, O(1) space — and the one subtlety is that after swapping a 2 the middle pointer must not advance.
INTERVIEW · vizlearn.in/interview/sort-colors-dutch-national-flag.html
More in Interview
Interview3SumInterviewSearch in a rotated sorted arrayInterviewSliding window maximumInterviewlist vs tuple vs deque vs array — which and why?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact