Dutch National Flag — Three-Way Partition

Before we start

In the last chapter we used a slow + fast pointer to separate keepers from junk. This chapter extends that to three zones — low, middle, high — using three pointers. By the end you will be able to:

• See the three-pointer partition as a concrete sorting action, like hands sorting laundry.
• Explain out loud why the algorithm is correct even though it processes elements in a scrambled order.
• Recognise this pattern in problems about 0s/1s/2s, two-part partitions, and flag-style sorting.

Stop at every Pause & Think box before reading on.

Picture this first (no code yet)

That laundry sorting is the Dutch National Flag algorithm. The left boundary is the low pointer, the right boundary is high, and your current position is mid.

The actual problem

You have an array containing only the values 0, 1, and 2 (in any order). Sort it in-place, using one pass, using O(1) extra space. After sorting: all 0s come first, then all 1s, then all 2s.

Example:

input  : [2, 0, 2, 1, 1, 0]
output : [0, 0, 1, 1, 2, 2]

The mapping to laundry: 0 = red, 1 = white, 2 = blue.

First, the slow way (so you feel the pain)

Approach 1 — count and rebuild:

Count how many 0s, 1s, and 2s exist, then overwrite the array:

from collections import Counter

def sort_colors_count(nums):
    c = Counter(nums)
    i = 0
    for val in [0, 1, 2]:
        for _ in range(c[val]):
            nums[i] = val
            i += 1

This works. Two passes — one to count, one to write. Time O(n), space O(1).

Approach 2 — general comparison sort:

nums.sort()   # O(n log n) — completely ignores the three-value structure

Wasteful. We know there are only three distinct values. A comparison sort does n log n comparisons when n comparisons suffice.

The Dutch National Flag algorithm does it in one pass, O(n) time, O(1) space — twice as fast as counting and infinitely faster than general sort.

The turning point

Think about the counting approach. Why does it need two passes? Because on the first pass it only reads — it doesn't know where to put things until the counts are complete.

Here's the insight. You don't need to know how many of each value exists. You only need to maintain one fact at every moment:

"Everything to the left of low is a 0. Everything to the right of high is a 2. Everything between low and mid is a 1."

As long as that statement is always true, when mid and high finally meet, the whole array is sorted. You just need to make every new element you examine immediately true to that statement.

The one idea to remember

Watch it happen, frame by frame

Array: [2, 0, 2, 1, 1, 0]

We start with low = 0, mid = 0, high = 5.

State:  low=0  mid=0  high=5
Array: [2, 0, 2, 1, 1, 0]
        ↑                ↑
       mid             high
       low

mid element = 2  →  BLUE → swap nums[mid] with nums[high], high--
Array: [0, 0, 2, 1, 1, 2]   (high shrinks to 4, mid stays at 0)

State:  low=0  mid=0  high=4
Array: [0, 0, 2, 1, 1, 2]
        ↑             ↑
       mid           high
       low

mid element = 0  →  RED → swap nums[mid] with nums[low], low++, mid++
Array: [0, 0, 2, 1, 1, 2]   (self-swap, both advance)
low=1, mid=1

State:  low=1  mid=1  high=4
Array: [0, 0, 2, 1, 1, 2]

mid element = 0  →  RED → swap nums[1] with nums[1], low=2, mid=2
Array unchanged.

State:  low=2  mid=2  high=4
Array: [0, 0, 2, 1, 1, 2]
              ↑       ↑
             mid     high

mid element = 2  →  BLUE → swap nums[mid] with nums[high], high--
Array: [0, 0, 1, 1, 2, 2]   high=3

State:  low=2  mid=2  high=3
Array: [0, 0, 1, 1, 2, 2]
              ↑    ↑
             mid  high

mid element = 1  →  WHITE → mid++
mid=3

State:  low=2  mid=3  high=3
Array: [0, 0, 1, 1, 2, 2]
                 ↑
              mid=high

mid element = 1  →  WHITE → mid++
mid=4  >  high=3  →  STOP

Final: [0, 0, 1, 1, 2, 2]  ✅

low=0, mid=0, high=4
mid=1 (white) → mid=1
mid=2 (blue)  → swap(1,4), high=3. Array:[1,2,0,1,2]→[1,2,0,1,2] wait:
  swap nums[1] and nums[4]: [1,2,0,1,2]. Hmm, let's be careful.
  nums[mid]=nums[0]=1 → white → mid++

low=0, mid=1, high=4
nums[mid]=nums[1]=2 → blue → swap(nums[1],nums[4]), high=3
Array: [1,2,0,1,2] → swap index 1 and 4 → [1,2,0,1,2] ... nums[4]=2, nums[1]=2, same → [1,2,0,1,2], high=3

low=0, mid=1, high=3
nums[mid]=nums[1]=2 → blue → swap(nums[1],nums[3]), high=2
Array: [1,1,0,2,2], high=2

low=0, mid=1, high=2
nums[mid]=nums[1]=1 → white → mid=2

low=0, mid=2, high=2
nums[mid]=nums[2]=0 → red → swap(nums[0],nums[2]), low=1, mid=3
Array: [0,1,1,2,2]

mid=3 > high=2 → STOP
Final: [0, 1, 1, 2, 2]  ✅

Now, the code — line by line

def sort_colors(nums):
    low = 0               # boundary: everything left of low is a 0
    mid = 0               # current element being examined
    high = len(nums) - 1  # boundary: everything right of high is a 2

    while mid <= high:    # unsorted middle exists while mid hasn't crossed high
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]  # red → send to left section
            low += 1      # left boundary grows
            mid += 1      # element at new mid was a known 1 (from left section), so advance
        elif nums[mid] == 2:
            nums[mid], nums[high] = nums[high], nums[mid]  # blue → send to right section
            high -= 1     # right boundary shrinks
            # DO NOT advance mid — the swapped-in element is unseen
        else:
            mid += 1      # white (1) → already in the right place, just move on

Every line mapped to the laundry story:

• low = 0 — the left boundary of the sorted red pile starts empty at position 0.
• high = len(nums) - 1 — the right boundary of the sorted blue pile starts empty at the last position.
• mid = 0 — you stand at the very first item in the unsorted pile.
• while mid <= high: — keep sorting while there's still unsorted middle ground between your hands.
• nums[mid] == 0 → swap to the left, push both boundaries inward. The item that was at low was a 1 (proven by the invariant), so mid can safely advance.
• nums[mid] == 2 → swap to the right, pull the right boundary in. Do not advance mid — the item that just arrived from position high has never been examined.
• else (it's a 1) → it belongs in the middle; just step over it.

Why does it never go wrong?

The algorithm stays correct because of one invariant it maintains at all times:

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

• Everything left of low is guaranteed to be a 0.
• Everything between low and mid is guaranteed to be a 1.
• Everything between mid and high (inclusive) is unknown.
• Everything right of high is guaranteed to be a 2.

Every operation preserves this invariant:

• Swap a 0 to the left: low region gains a 0, the 1 displaced goes to the middle region, mid advances. ✓
• Swap a 2 to the right: high region gains a 2, the swapped-in element is unknown so it joins the unsorted middle. ✓
• Skip a 1: it was already in the middle region. ✓

When mid > high, the unsorted region is empty. The invariant then covers the entire array — it's perfectly sorted. □

Why is it so fast?

Every element is examined by mid exactly once. After any swap, either mid advances (making progress toward high) or high retreats (shrinking the unsorted zone). The total number of pointer moves is bounded by n. No element is ever touched more than twice (once by mid, at most once by a swap).

n = 1,000,000  →  at most 2,000,000 operations
General sort   →  ~20,000,000 comparisons (n log n)
Two-pass count →  exactly 2n operations (two passes)
DNF            →  ≤ 2n operations (one pass)

When should I reach for this? (the trigger list)

Reach for three-pointer partition when you see:

• An array with exactly 3 distinct values (or categories) that need to be grouped.
• "Sort in-place using one pass" — the signature of DNF.
• A two-pointer partition problem where one of the "keep" values actually needs to go to two different places (front vs. back vs. middle).
• Problems about 0s, 1s, 2s; negative, zero, positive; less than, equal to, greater than pivot.
• Binary partition problems (two-way, using only low and high without mid) — DNF generalises those.

The same trick in four disguises

Disguise 1 — Sort Colors (LC #75)

The exact problem above. Identical code. This is the canonical DNF problem.

Disguise 2 — Separate Negatives, Zeros, Positives

Three categories: negative (0), zero (1), positive (2). Same three pointers, same skeleton, different value labels:

def sort_by_sign(nums):
    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] > 0:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1

Same bones. Only the "what counts as 0/1/2" changes.

Disguise 3 — Move all zeroes and ones to ends (custom problem)

"Given an array of 0s, 1s, and 2s, move 0s to the front and 2s to the back, with 1s in the middle." That is literally the DNF problem stated differently. Use the exact same code.

Traps that catch beginners

Say it like a pro (interview one-liner)

"Since there are exactly three distinct values, I'll use the Dutch National Flag algorithm — three pointers maintaining the invariant that everything left of low is a 0, everything between low and mid is a 1, and everything right of high is a 2. Each element is examined exactly once, giving O(n) time and O(1) space in a single pass."

Check yourself

Practice problems

When you can write the Sort Colors solution from scratch, explain why mid doesn't advance after a blue swap, and state the invariant in one sentence — you have fully learned this pattern.

Next up: Sliding Window — Fixed Size, where instead of pointers on individual elements, we maintain a whole window of K elements as it slides across the array.