Dutch National Flag
The Dutch National Flag (DNF) problem asks: given an array whose elements take only three distinct values (call them
<,=,>a pivot, or red/white/blue, or 0/1/2), rearrange the array in a single pass with O(1) extra space so that all<come first, all=come next, and all>come last. Edsger W. Dijkstra posed and solved it as a teaching exercise in invariant-driven program design, presented as a chapter of his A Discipline of Programming (Prentice-Hall, 1976) (Wikipedia: Dutch national flag problem). He returned to the flag motif in his manuscript EWD608, “An elephant inspired by the Dutch National Flag” (EWD608), though that note is a separate concurrency/termination exercise that merely borrows the flag image rather than the partitioning problem itself. The clean three-pointer solution —low,mid,highwalking once through the array with carefully asymmetric updates — is the canonical building block for the three-way Quicksort partition that handles arrays with many duplicate keys in O(n) per level instead of degenerating to O(n²). The same template generalizes to any “partition into three buckets defined by comparison to a key” problem.
1. Intuition — Sorting a Box of Three-Colored Balls
Imagine a long, narrow box with n colored balls in random order: red, white, and blue. You want red on the left, white in the middle, blue on the right, and you can do it only by swapping adjacent positions or any two positions you can point at simultaneously — in one pass, without taking the balls out of the box, and without writing anything down.
Use three fingers as bookmarks:
- A low finger that marks the boundary between finished red region and the rest. Everything to the left of
lowis confirmed red. - A high finger that marks the boundary between the rest and finished blue region. Everything to the right of
highis confirmed blue. - A mid finger that walks rightward from
lowexamining the next unclassified ball.
For each ball that mid looks at:
- If it’s white, leave it alone (white belongs in the middle), and slide
midright. - If it’s red, it belongs on the left — swap it with whatever’s at
low, slide bothlowandmidright. - If it’s blue, it belongs on the right — swap it with whatever’s at
high, slidehighleft, but do not slidemidbecause the ball that just arrived from the right is still unexamined.
When mid passes high, the unclassified middle has shrunk to nothing and the box is sorted. Each ball is touched O(1) times; the total work is O(n).
The asymmetry is the whole pedagogical point. When you swap a red into the low slot, the value that comes back was previously inspected by mid (which is why mid is past low in the first place — it was a 1/white, otherwise mid would have stopped). When you swap a blue out, the value that comes back from high has never been inspected, so mid must re-examine it on the next iteration. Get that asymmetry wrong and you either mis-sort or infinite-loop. The Dutch Flag problem is in every algorithms curriculum precisely because this asymmetry is a tiny, concrete instance of “the loop invariant must hold at every iteration boundary, and updates that violate it are bugs no matter how plausible they look.”
2. Tiny Worked Example
Take arr = [2, 0, 2, 1, 1, 0]. Treat 0 as red, 1 as white, 2 as blue. Initial pointers: low = 0, mid = 0, high = 5.
The invariant we maintain at every step:
arr[0 .. low - 1]are all0sarr[low .. mid - 1]are all1sarr[mid .. high]are unclassifiedarr[high + 1 .. n - 1]are all2s
| Step | low | mid | high | arr | arr[mid] | Action |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 5 | [2, 0, 2, 1, 1, 0] | 2 | swap(mid=0, high=5), high— |
| 1 | 0 | 0 | 4 | [0, 0, 2, 1, 1, 2] | 0 | swap(low=0, mid=0), low++, mid++ |
| 2 | 1 | 1 | 4 | [0, 0, 2, 1, 1, 2] | 0 | swap(low=1, mid=1), low++, mid++ |
| 3 | 2 | 2 | 4 | [0, 0, 2, 1, 1, 2] | 2 | swap(mid=2, high=4), high— |
| 4 | 2 | 2 | 3 | [0, 0, 1, 1, 2, 2] | 1 | mid++ |
| 5 | 2 | 3 | 3 | [0, 0, 1, 1, 2, 2] | 1 | mid++ |
| 6 | 2 | 4 | 3 | — | — | mid > high, stop |
Final: [0, 0, 1, 1, 2, 2]. Six iterations for six elements, three swaps. Notice that step 1 and step 2 both swap an element with itself (low == mid); the Python-idiomatic write still happens but is a no-op, and the pointers advance — that’s the intended degenerate case. The algorithm doesn’t special-case it.
3. The Pattern Recognition Signal
Reach for Dutch National Flag when:
- The input has exactly three categories (or, more generally, you want to partition into three regions). Most often this is
< pivot,= pivot,> pivot; or three colors; or three states (e.g., even / zero / odd). - You need O(n) time and O(1) extra space — the obvious counting-sort-style approach (
count_0, count_1, count_2, then overwrite) is also O(n)/O(1) and arguably simpler, but Dutch Flag is single-pass (counting-sort makes two passes) and is the natural building block when the categorization predicate is more expensive than equality. - You’re partitioning around a pivot for Quicksort and the input has many duplicate keys. Three-way partitioning prevents Quicksort’s worst-case O(n²) degeneration on inputs like
[5, 5, 5, ..., 5]by sweeping all the duplicates into the equal region in a single pass, then recursing only on<and>halves. - The problem mentions Dijkstra, “three-way partition,” “sort colors,” “Dutch flag,” or LC 75 explicitly.
The pattern is one of those rare cases where naming it correctly during a whiteboard session (“this is the Dutch National Flag problem; I’ll use Dijkstra’s three-pointer scheme”) buys you significant credit even before writing code.
4. Pseudocode
dutch_flag(arr):
low := 0
mid := 0
high := length(arr) - 1
while mid <= high:
if arr[mid] < pivot: # belongs to LEFT region
swap(arr[low], arr[mid])
low := low + 1
mid := mid + 1
else if arr[mid] == pivot: # belongs to MIDDLE region
mid := mid + 1
else: # arr[mid] > pivot, belongs to RIGHT region
swap(arr[mid], arr[high])
high := high - 1
# do NOT advance mid: the value swapped in is still unclassified
The pointer-update pattern is the only correct one; the tempting symmetric update (mid := mid + 1 after the right-swap, mirroring the left-swap) is the most common bug. Trace through [2, 0] by hand under both rules and you’ll see why: with the wrong rule, the 0 from position 1 ends up on the right, sorted as if it were a 2.
5. Python Implementation
5.1 Sort Colors (LC 75) — The Canonical Example
def sort_colors(nums: list[int]) -> None:
"""Sort an array containing only 0, 1, 2 in place, in one pass."""
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # do NOT advance mid here5.2 Three-Way Partition Around an Arbitrary Pivot
def three_way_partition(arr: list[int], pivot: int) -> tuple[int, int]:
"""Partition arr in place; return (low, high+1) so that:
arr[:low] < pivot, arr[low:high+1] == pivot, arr[high+1:] > pivot.
"""
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
if arr[mid] < pivot:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == pivot:
mid += 1
else:
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
return low, high + 1The return values (low, high + 1) give the boundaries of the equal-to-pivot region as a half-open interval, idiomatic for slicing in Python. After this call, arr[:low] strictly less than pivot, arr[low:high+1] equal to pivot, arr[high+1:] strictly greater.
5.3 Three-Way Quicksort (Bentley & McIlroy 1993, “Engineering a Sort Function”)
def quicksort_3way(arr: list[int], lo: int = 0, hi: int | None = None) -> None:
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return
pivot = arr[(lo + hi) // 2]
low, mid, high = lo, lo, hi
while mid <= high:
if arr[mid] < pivot:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == pivot:
mid += 1
else:
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
quicksort_3way(arr, lo, low - 1)
quicksort_3way(arr, high + 1, hi)
# the equal-to-pivot middle region needs no further sortingThis variant is what makes Quicksort competitive on input with many duplicate keys. The standard two-way partition recurses on a half that may be mostly == pivot, performing a useless O(n) re-partition each time and degrading to O(n²) on [k, k, k, ..., k]. The three-way partition collapses the entire equal-to-pivot region in a single pass and recurses only on the strictly smaller and strictly larger halves; on input with O(d) distinct keys, three-way Quicksort runs in O(n log d) rather than O(n log n) — a strict improvement when d ≪ n.
Bentley and McIlroy’s 1993 paper “Engineering a Sort Function” (published in Software: Practice and Experience) introduced the production-grade variant of this scheme that became the basis for qsort in many C libraries; it uses the Dutch Flag idea in a slightly different layout (swap equal elements to both ends during the partition, then move them to the middle in a final pass), but the underlying combinatorial idea is Dijkstra’s.
6. Complexity
Time: O(n). Every iteration of the while loop either advances mid by 1 or moves high left by 1. Both pointers are bounded — mid from 0 to n - 1, high from n - 1 to 0. Their meeting point bounds the total iteration count at n. Each iteration does O(1) work (comparison and possibly a swap). Therefore O(n) total.
A more careful analysis: count the swaps explicitly. A swap with low happens when we see a 0, at most once per 0 in the input; a swap with high happens when we see a 2, at most once per 2. The number of swaps is therefore count(0) + count(2) ≤ n.
Space: O(1). Three integer pointers and a constant number of temporaries for the swaps. The algorithm rearranges the input in place; no auxiliary arrays.
Why one pass beats counting-sort. Counting-sort on three buckets is also O(n)/O(1), but it makes two passes over the array (one to count, one to overwrite). For input that already lives in fast cache, the difference is negligible; for very large arrays where pass count matters (e.g., streaming data, external memory), Dutch Flag’s single-pass nature is a real win. More importantly, Dutch Flag generalizes to predicates that are expensive to evaluate twice (e.g., the comparison is to a computed pivot derived from the swept-in elements themselves) — there counting-sort isn’t directly applicable.
7. Variants and Extensions
7.1 Two-Way Partition (Lomuto and Hoare Schemes)
If you only have two categories (<= pivot and > pivot), drop to a two-pointer partition. The Lomuto scheme uses a single read/write pointer pair; Hoare’s original 1962 partition uses converging pointers from both ends. Both are simpler than Dutch Flag and used inside two-way Quicksort. Dutch Flag is strictly more general: it’s two-way partition’s three-way upgrade.
7.2 K-Way Partition
For k > 3 categories, the Dutch Flag generalization gets fiddly; in practice you either run multiple passes (each a Dutch Flag against one boundary) or fall back to Counting Sort if the categories are integer-valued. There’s no standard one-pass k-way in-place partition for arbitrary k, and the constant factors of trying make multi-pass approaches more practical past k = 4.
7.3 Sort by Predicate (Move Zeros, Partition by Parity, etc.)
The “partition” variant of Two Pointers is the special case of Dutch Flag where there are only two buckets and the boundary is a write head. Use it for “move all zeros to end,” “partition array by parity,” “remove element,” etc. Dutch Flag adds the third bucket; degenerate to two-way when you don’t need the third.
7.4 Functional / Immutable Variants
In immutable-data settings (Haskell, Clojure, persistent data structures), the in-place Dutch Flag is replaced by a single-pass foldr that builds three accumulator lists and concatenates. The three-bucket idea survives; the in-place mechanics don’t. Asymptotic complexity is preserved at O(n)/O(n) for the immutable version.
7.5 The 4-Color Variant (Dutch + One More)
Dijkstra also discussed a four-color extension; the four-pointer scheme is uglier and rarely seen in practice. By the time you have four categories the cleaner approach is two-pass (split into two buckets at the median, then Dutch-Flag each half).
8. Pitfalls
8.1 Advancing mid After the High-Swap
The single most common bug. After swap(arr[mid], arr[high]); high -= 1, you must not advance mid because the value swapped in from the high end has not been classified yet. Advancing mid skips that examination and produces sorted output that occasionally has a 0 or 1 stranded in the right region. Symptom on LC 75: passes [2, 0, 1] but fails [2, 0, 2, 1, 1, 0].
8.2 Loop Condition mid <= high vs. mid < high
Use <=, not <. When mid == high, the element at position mid is still unclassified and must be processed; using < exits the loop one iteration early and leaves that element in the wrong region. The classic single-element edge case [0], [1], [2] exposes this bug immediately.
8.3 Initializing high = len(arr) Instead of len(arr) - 1
Dutch Flag uses closed intervals on both sides ([low, mid - 1] = 1s, [mid, high] = unknown, [high + 1, n - 1] = 2s). Initializing high = len(arr) would index out of bounds on the first high-swap. Stick with high = len(arr) - 1.
8.4 Confusing the Order of low-Swap Updates
After swap(arr[low], arr[mid]), you must increment both low and mid. Incrementing only low leaves mid pointing at the just-placed 0, which on the next iteration triggers another low-swap with itself and re-increments low past where it should be. The (low, mid) double-increment is the symmetric counterpart to the high-side’s single decrement of high.
8.5 Reusing the Pattern for Two Categories
Dutch Flag is overkill for two categories. If you only need < pivot and >= pivot, use a simpler two-pointer partition (Lomuto or Hoare). Dutch Flag’s complexity (three pointers, asymmetric updates) is worth it only when you genuinely need three buckets — overengineering it as a two-way partition just makes the code harder to read for no benefit.
8.6 Using It on Stream Data Without Knowing n
The algorithm requires random-access indexing (you swap arr[mid] with arr[high]); it can’t run on a stream where you can’t address arr[high]. For streaming three-way partition you need a different (multi-pass or buffered) approach.
8.7 Forgetting Three-Way Quicksort’s Pivot Choice Still Matters
Three-way Quicksort handles duplicate keys gracefully, but it’s still a Quicksort — pivot choice still matters for worst-case behavior on (rare) adversarial sorted input. Use median-of-three or randomization for production code, just as you would in two-way Quicksort.
9. Diagram — The Three Regions and the Sweep
flowchart LR subgraph state ["Invariant during the loop"] L0["arr[0 .. low-1]<br/>all = 0 (red)"]:::red L1["arr[low .. mid-1]<br/>all = 1 (white)"]:::white L2["arr[mid .. high]<br/>UNCLASSIFIED"]:::unknown L3["arr[high+1 .. n-1]<br/>all = 2 (blue)"]:::blue L0 --> L1 --> L2 --> L3 end classDef red fill:#ff6b6b,stroke:#000,color:#000 classDef white fill:#fff,stroke:#000,color:#000 classDef unknown fill:#dddddd,stroke:#000,color:#000 classDef blue fill:#6b9eff,stroke:#000,color:#000
What this diagram shows. At every iteration of the Dutch Flag main loop, the array is partitioned into four contiguous regions: the confirmed-red prefix arr[0..low-1], the confirmed-white middle arr[low..mid-1], the unclassified region arr[mid..high], and the confirmed-blue suffix arr[high+1..n-1]. The loop’s job is to shrink the unclassified middle region by one element per iteration — either by advancing mid rightward (when arr[mid] is white or after a swap with low) or by decrementing high leftward (after a swap to deposit a blue at the back). The loop terminates when the unclassified region is empty, i.e., mid > high. The colors of the Dutch national flag (red top, white middle, blue bottom) inspired Dijkstra’s framing — though the sorted output is conventionally drawn left-to-right rather than top-to-bottom.
10. Common Interview Problems
| # | Problem | Variant of Dutch Flag |
|---|---|---|
| LC 75 | Sort Colors | Canonical, three values 0/1/2 |
| LC 215 | Kth Largest Element in Array | Three-way Quickselect uses Dutch Flag partition |
| LC 905 | Sort Array By Parity | Two-way partition (degenerate Dutch Flag) |
| LC 922 | Sort Array By Parity II | Two-way partition with offset constraint |
| LC 280 | Wiggle Sort | Multi-criterion partition; Dutch Flag in spirit |
| LC 324 | Wiggle Sort II | Three-way partition around the median |
| LC 148 | Sort List | Three-way partition variant for linked-list quicksort |
| LC 1366 | Rank Teams by Votes | Sort with custom comparator; uses partitioning ideas |
The Quickselect/median-of-medians family in particular benefits from three-way partitioning when the array contains many duplicates of the pivot — a worst-case input for two-way Quickselect that three-way handles in stride.
11. Open Questions
- Is there a Dutch-Flag-like single-pass scheme for
k = 4categories that doesn’t degenerate to two passes? Some attempts in the literature exist but none have the elegance of the three-pointer scheme. - Does branch prediction matter for Dutch Flag in modern CPUs? The three-way conditional inside the loop can be hostile to branch prediction on adversarial input; some analyses suggest a branch-free variant using arithmetic on the comparison results is faster on random input but slower on already-partitioned input.
Uncertain uncertain
Verify: that a branch-free arithmetic Dutch-Flag variant is faster than the branching version on random input and slower on already-partitioned input. Reason: this is an empirical, micro-architecture-dependent claim not pinned to a primary benchmark consulted for this note; the magnitude and even the sign of the effect vary across CPUs, compilers, and element types. To resolve: run a controlled benchmark (e.g. on a known microbenchmark harness) across random vs. sorted vs. all-equal inputs and several element widths, or cite a published study (such as the branchless-partition analyses in the BlockQuicksort / “Branch Mispredictions Don’t Affect Mergesort” line of work) that measures it directly.
- Is there a clean parallel version? Each prefix/suffix can be Dutch-Flagged independently, then the regions stitched together — but the stitching requires a synchronized merge that may dominate.
12. See Also
- Two Pointers — Dutch Flag is its three-pointer generalization; the partition variant of two pointers is the two-bucket degenerate case
- Quicksort — three-way Quicksort uses Dutch Flag as its partition step; the canonical use case
- Cyclic Sort — sibling in-place pattern for a different precondition (
1..npermutations) - Counting Sort — alternative O(n)/O(k) approach when the categories are small integer values; two-pass instead of one
- Insertion Sort — simpler in-place sort, used as the base case below the Quicksort cutoff
- Merge Sort — alternative O(n log n) sort that avoids partition issues entirely at the cost of O(n) extra space
- Big-O Notation — for the O(n) argument
- SWE Interview Preparation MOC