Dutch National Flag and In-place Partitioning

Sorting an array of three distinct values is the shortest problem in this phase with a genuinely subtle answer. Counting sort does it in two passes and is a perfectly good answer. The interviewer will then ask for one pass, and that is where the Dutch national flag algorithm comes in — named by Dijkstra after the Dutch flag’s three horizontal bands.

It is worth learning for a reason beyond LeetCode 75: three-way partitioning is what makes quicksort survive an array of mostly-equal values, which is the input that turns naive quicksort quadratic.

What you’ll learn

• The three-region invariant and why maintaining it needs exactly three pointers.
• Why mid advances on a 0 and a 1 but not on a 2 — the one line that decides correctness.
• Why three-way partitioning fixes quicksort’s worst case on duplicate-heavy input.
• The variants: partition around a pivot, move zeroes, sort by parity.

The cue

You are looking at three-way partitioning when…

• The values fall into exactly three categories — 0/1/2, negative/zero/positive, less-than/equal-to/greater-than a pivot — and you must group them in order.
• The problem demands one pass and $O(1)$ space, which rules out counting sort (two passes) and any auxiliary array.
• Or you are partitioning around a pivot and the array contains many duplicates of it.

The invariant is the algorithm. At every step the array is four regions:

text

[ 0 .. low-1 ]  [ low .. mid-1 ]  [ mid .. high ]  [ high+1 .. n-1 ]
   all 0s            all 1s          UNKNOWN          all 2s

The loop shrinks the unknown region to nothing. Once you can state those four regions, the code writes itself — and once you cannot, no amount of pointer fiddling will recover it.

Reach for something else when there are more than three categories (counting sort, or a plain sort), or when two categories suffice (a single read/write pointer — that is two pointers).

Visual intuition

Watch the unknown region collapse from both ends, and watch what mid does on a 2:

arrayThree regions, one pass, and one pointer that does not always advanceLC 75 · O(n) time, O(1) space

unknown

200122131405

lowmidhigh

1def sort_colors(arr):2    low, mid, high = 0, 0, len(arr) - 13    while mid <= high:4        if arr[mid] == 0:5            arr[low], arr[mid] = arr[mid], arr[low]6            low += 1; mid += 17        elif arr[mid] == 1:8            mid += 19        else:                      # == 210            arr[mid], arr[high] = arr[high], arr[mid]11            high -= 1              # mid does NOT advance

setupThree regions, one pass: everything left of low is 0, everything right of high is 2, and low..high is still unknown. The loop shrinks the unknown region to nothing.

Play‹›1/8⟲

On a 2 the value swapped in from the right has not been examined yet, so mid must stay put. Advancing there is the defining bug: it passes many inputs and silently leaves a 2 stranded in the middle.

The template

dutch_national_flag.py

def sort_colors(arr):                       # LC 75
    low, mid, high = 0, 0, len(arr) - 1
    while mid <= high:                       # <= , not < : high is inclusive
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1                         # swapped-in value is a known 1
        elif arr[mid] == 1:
            mid += 1                         # already in the right region
        else:                                # == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1                        # mid does NOT advance
    return arr
 
 
def three_way_partition(arr, pivot):         # the quicksort building block
    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                         # arr[low..high] all == pivot
 
 
print(sort_colors([2, 0, 2, 1, 1, 0]))       # expect [0, 0, 1, 1, 2, 2]
print(three_way_partition([3, 1, 3, 5, 3, 2], 3))  # expect (2, 3)

Dry run

arr = [2, 0, 2, 1, 1, 0]. The action column is what to narrate aloud.

step	array	low	mid	high	arr[mid]	action
1	[2,0,2,1,1,0]	0	0	5	2	swap mid↔high; high→4; mid stays
2	[0,0,2,1,1,2]	0	0	4	0	swap mid↔low; low→1, mid→1
3	[0,0,2,1,1,2]	1	1	4	0	swap mid↔low; low→2, mid→2
4	[0,0,2,1,1,2]	2	2	4	2	swap mid↔high; high→3; mid stays
5	[0,0,1,1,2,2]	2	2	3	1	mid→3
6	[0,0,1,1,2,2]	2	3	3	1	mid→4
7	—	2	4	3	—	mid > high, loop ends

Result [0, 0, 1, 1, 2, 2]. Six elements, seven iterations, and every element moved at most twice.

Read step 1 and step 4 together. Both saw a 2 and both left mid where it was. At step 1 the value swapped in was a 0 — still unexamined. Advance mid there and that 0 is stranded to the right of low forever, and the output is [2,0,...]-shaped garbage.

Three details, each of which breaks it

1. while mid <= high, not <. high is an inclusive boundary, so the element at high still needs examining. With < the last element is skipped.
2. mid does not advance on a 2. The value arriving from the right is unknown. This is the defining bug of the algorithm.
3. mid does advance on a 0. The value swapped in from low is necessarily a 1 — because everything in low..mid-1 is a 1 by the invariant — so it needs no re-examination. That asymmetry is not arbitrary; it follows from the invariant.

Complexity

Approach	Passes	Time	Space
Built-in sort()	—	$O(n \log n)$	$O(n)$ (Timsort)
Counting sort	2	$O(n)$	$O(1)$ — three counters
Dutch national flag	1	$O(n)$	$O(1)$

Each element is swapped at most twice — once into the 0 region, once into the 2 region — so the constant factor is small. Counting sort is equally $O(n)$ and much easier to write; the only thing DNF buys is the single pass. Say that plainly, and offer counting sort first if the problem does not demand one pass — volunteering the simpler correct answer before the clever one reads well.

The variant map

Variant	Change	Canonical problem
Sort 0/1/2	the base template	75 Sort Colors
Partition around a pivot	compare < pivot, == pivot, > pivot	quicksort with duplicates
Two categories only	one write pointer, no high	283 Move Zeroes · 905 Sort By Parity
Move zeroes to the end, order preserved	two pointers, no third region	283 Move Zeroes
Wiggle / rearrange	the same partition then interleave	324 Wiggle Sort II
Quickselect with duplicates	recurse only into the < or > region	215 Kth Largest

This is what fixes quicksort on duplicate-heavy input

Standard Lomuto partitioning splits into < pivot and >= pivot. Feed it an array where every value is equal and one side gets everything — the recursion depth becomes $n$ and quicksort degrades to $O(n^2)$.

Three-way partitioning puts all copies of the pivot in the middle and recurses only into the two outer regions. An array of all-equal values is then sorted in a single partition step. This is why production quicksorts (and quickselect implementations) use three-way partitioning, and it is a strong follow-up answer to “how would you make quicksort robust”.

Pitfalls

• Advancing mid after a 2 swap. The single most common failure. The incoming value is unexamined.
• while mid < high. high is inclusive; the final element is skipped and the bug appears only on certain inputs.
• Swapping with low and then not advancing mid. The opposite error — this causes an infinite loop when low == mid.
• Using it for more than three categories. The invariant does not generalise; use counting sort.
• Reaching for it when two categories suffice. Move Zeroes needs one write pointer, not three. The extra pointer is complexity for nothing.
• Not offering counting sort first. If the problem does not demand one pass, the two-pass version is simpler and equally optimal — and saying so is a signal, not a weakness.

Interview follow-ups

They ask	What they’re checking	The answer
“Why does mid not advance on a 2?”	Whether you understand or memorised	The value swapped in from high has never been examined. Advancing strands it
“Then why does it advance on a 0?”	Depth of the invariant	The value swapped in from low is necessarily a 1, because low..mid-1 holds only 1s. It needs no re-examination
“Can you do it in two passes?”	Whether you know the simpler answer	Counting sort: count the three values, then overwrite. Same $O(n)$, far easier, and the right answer unless one pass is required
“Generalise to k categories”	Boundaries	The invariant does not extend past three. Use counting sort — $O(n + k)$
“How does this help quicksort?”	Whether you see the connection	Three-way partitioning puts equal values in the middle and recurses only into the outer regions, so an all-equal array is sorted in one partition instead of degrading to $O(n^2)$
“Is it stable?”	Precision	No. Swapping across the array reorders equal elements. If stability matters, use a stable sort or an auxiliary array

Practice

3 problems

1 easy2 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○283Move Zeroeseasy
• ○75Sort Colorsmediumamazonmicrosoftmeta
• ○324Wiggle Sort IImedium

Exercises

LC 75 — Sort Colors · Medium

pch.exerciseTag pch.exerciseTitle

Three-way partition around a pivot

pch.exerciseTag pch.exerciseTitle

LC 283 — Move Zeroes · Easy (the two-category case)

pch.exerciseTag pch.exerciseTitle

Self-check

pch.quizTag Dutch national flag — self-check

1. Why does `mid` not advance after swapping a 2 to the right?

   A To keep the loop bounded B Because the value swapped in from `high` has never been examined — advancing would strand it C Because `high` already decremented D It should advance; that is a bug in the standard version
   pch.quizShowAnswer

   B — Because the value swapped in from `high` has never been examined — advancing would strand it — This is the defining detail. Advancing here passes many inputs and silently leaves an unexamined value in the middle region, so the failure is intermittent and hard to spot.

2. Then why DOES `mid` advance after swapping a 0 to the left?

   A For symmetry with the 1 case B Because the value swapped in from `low` is necessarily a 1 — everything in low..mid-1 is a 1 by the invariant — so it needs no re-examination C Because `low` and `mid` are always equal D It is an optimisation and could be omitted
   pch.quizShowAnswer

   B — Because the value swapped in from `low` is necessarily a 1 — everything in low..mid-1 is a 1 by the invariant — so it needs no re-examination — The asymmetry follows from the invariant rather than being arbitrary. Being able to derive it is what separates understanding the algorithm from having memorised it.

3. Why is the loop condition `mid <= high` rather than `mid < high`?

   A To handle the empty array B Because `high` is an inclusive boundary — the element at `high` still needs examining, and `<` would skip the last element C To avoid an infinite loop D They are equivalent
   pch.quizShowAnswer

   B — Because `high` is an inclusive boundary — the element at `high` still needs examining, and `<` would skip the last element — Boundary convention decides the comparison. With an inclusive `high`, `<` leaves one element unprocessed, and the bug shows only on inputs where that element is out of place.

4. The interviewer has not asked for one pass. What do you offer first?

   A Dutch national flag, since it is optimal B Counting sort — two passes, same O(n) time, far simpler and equally correct — then mention DNF if one pass is required C The built-in sort() D Quickselect
   pch.quizShowAnswer

   B — Counting sort — two passes, same O(n) time, far simpler and equally correct — then mention DNF if one pass is required — Volunteering the simpler correct answer before the clever one reads as judgement, not weakness. DNF's only advantage is the single pass, so it should be justified by a stated requirement.

5. How does three-way partitioning fix quicksort on duplicate-heavy input?

   A It changes the pivot selection B It puts all copies of the pivot in the middle and recurses only into the outer regions, so an all-equal array is sorted in one partition step rather than degrading to O(n squared) C It makes the sort stable D It reduces the space to O(1)
   pch.quizShowAnswer

   B — It puts all copies of the pivot in the middle and recurses only into the outer regions, so an all-equal array is sorted in one partition step rather than degrading to O(n squared) — Standard Lomuto splits into < and >=, so an all-equal array sends everything to one side and the recursion depth becomes n. This is why production quicksorts partition three ways.

Recall card

• Cue — exactly three categories, one pass, $O(1)$ space. Two categories need only one write pointer; more than three need counting sort.
• Invariant — [0, low) all lows · [low, mid) all middles · [mid, high] unknown · (high, n) all highs.
• Template — while mid <= high: on low, swap with low and advance both; on middle, advance mid; on high, swap with high, decrement high, and leave mid.
• The three breakages — < instead of <=; advancing mid on a high; not advancing mid on a low.
• Complexity — $O(n)$, one pass, at most two swaps per element, not stable.
• Offer counting sort first unless one pass is required.
• Quicksort connection — three-way partitioning is what stops duplicate-heavy input degrading to $O(n^2)$.

Recap

• Three-way partitioning maintains four regions and shrinks the unknown one to nothing in a single pass.
• The whole algorithm is the invariant: state the four regions and the branches follow, including why mid advances on a low but not on a high.
• Counting sort is equally optimal and simpler; DNF’s only advantage is the single pass, so justify it against a stated requirement.
• The same partition makes quicksort robust against arrays of mostly-equal values, which is its real-world use.

Next: Trie Patterns — prefix trees applied to grid search and wildcard matching.