Dutch National Flag — Three Buckets in One Pass

Dijkstra’s Dutch National Flag algorithm rearranges an array of values from a tiny alphabet—classically 0, 1, and 2—into three contiguous regions in one linear scan with constant extra memory. It is the conceptual parent of three-way quicksort partitions.

Why this shows up in the real world

Imagine a quality control belt where each item is labeled only “scrap / rework / ship.” You must physically slide items into three lanes without a second conveyor. Streaming video codecs sometimes classify macroblocks into a few priority buckets that must be reordered before packing. Load balancers might tag requests {low, medium, high} and need them grouped for batch processing. Any time values come from a 3‑value enum and you need O(n) in-place clustering, this pattern appears.

Core idea (explained for students)

Keep three pointers: low tracks the end of the 0‑region, mid scans unknowns, and high tracks the start of the 2‑region. When a[mid] == 1, advance mid. When it is 0, swap with low and grow both low and mid. When it is 2, swap with high and shrink high without blindly incrementing mid (the new value at mid is unknown). This maintains the invariant that everything left of low is 0, between low and mid is 1, and right of high is 2.

Try this in Python

def sort012(nums: list[int]) -> None:
    lo = mid = 0
    hi = len(nums) - 1
    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1


a = [2, 0, 2, 1, 1, 0]
sort012(a)
print(a)

Common mistakes

• Incrementing mid after every swap with high—can skip a 0 or 1.
• Generalizing to many colors without a clear pointer strategy—different problem.
• Off-by-one when high starts at n-1.

Key takeaways

• O(n) time, O(1) extra space for three values.
• Foundation for three-way partition in quicksort with many duplicates.
• Great interview pattern: explain invariants before coding.