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.

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."

Overview

When an array contains only 0, 1, and 2, three pointers partition it into low, middle, and high regions in one pass. After swapping a high value from the right, recheck the current position.

In this guide
  1. Run it: Sort an array of 0s, 1s and 2s in code
  2. Three pointers, three regions
  3. Tracing it
  4. The counting alternative
  5. The invariant
  6. The one asymmetry
  7. The loop condition
  8. Where it comes from: quick sort
  9. The variants
  10. Sources and next steps

Run it: Sort an array of 0s, 1s and 2s in code

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.

Sources and next steps

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

Partition an array of 0s, 1s and 2s in one pass using three pointers. Watch low, mid and high converge until the array is sorted in place.

INTERVIEW · vizlearn.in/interview/sort-colors-dutch-national-flag.html

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.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.