Dutch National Flag Problem: Three-Pointer Partition and the Sort Colors Pattern

Back with another one in the series where I break down coding patterns that took me more than one attempt to understand. This is the Dutch National Flag problem, the LeetCode Sort Colors question, which I brute-forced with a counting trick for months before the elegant version clicked.

You have an array of three values, 0s, 1s, and 2s, jumbled together. Sort them so all the 0s come first, then the 1s, then the 2s, in a single pass and in place, without a real sort and without counting. That last constraint is the whole challenge.

Why the dutch national flag problem leetcode version is tricky

My first Sort Colors solution counted how many 0s, 1s, and 2s there were, then overwrote the array. It is O(n) and it passes, but it reads the array twice, and the follow-up asks for one pass without counting.

That is where I got stuck. How do you place a 2 correctly when you have not seen the rest of the array yet? The answer is you do not place things in their final spot. You partition. Once I switched from "where does this value go" to "which region does this value belong to," it opened up.

The name comes from Edsger Dijkstra, who used the Dutch flag's three bands of red, white, and blue as an analogy for partitioning into three groups. LeetCode packages it as problem 75, Sort Colors.

The three regions

As you sweep the array you maintain three growing regions and one shrinking unknown region. Everything before low is confirmed 0. Everything from low up to mid is confirmed 1. Everything after high is confirmed 2. Everything between mid and high is still unknown.

The pointer low marks where the next 0 lands, high marks where the next 2 lands, and mid is the scanner that walks the unknown region and classifies each element. The unknown region shrinks from both ends until mid passes high and the array is sorted. That framing is the entire algorithm.

The dutch national flag algorithm, case by case

You look at the element mid points to, and there are exactly three cases. If it is a 0, swap it to low, then advance both low and mid, because the element that came back was already scanned. If it is a 1, it is already in place, so just advance mid. If it is a 2, swap it with high and move high inward, but do not advance mid: the element pulled in from high has not been examined yet.

def sortColors(nums):
    low, mid = 0, 0
    high = 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
    return nums

The asymmetry between the 0 case and the 2 case is the trick. Swap a 0 forward and the returning element is already classified. Swap a 2 back and the returning element is a stranger. That is why one case advances mid and the other does not.

A quick trace

Trace [2, 0, 2, 1, 1, 0]. mid sees 2, so swap index 0 and 5, high drops to 4, giving [0, 0, 2, 1, 1, 2], mid stays. mid sees 0 twice, advancing low and mid to 2. mid sees 2, swap index 2 and 4, high drops to 3, giving [0, 0, 1, 1, 2, 2]. mid sees 1 twice and moves to 4, which passes high, so the loop stops. Sorted in one pass, and the 2s reached the back without any counting.

Complexity

Time is O(n), because mid and high travel a combined n steps before they cross. Space is O(1), since everything happens in place with three pointers. Same time as counting, but a genuine single pass with no separate write phase.

Mistakes I made

I advanced mid after swapping a 2, which strands stray 2s in the middle because you skip the unexamined element. If your output has misplaced 2s, this is almost always why. I also used mid < high instead of mid <= high, which skips the final element when the two pointers meet. And I moved high in branches other than the 2 case, which breaks the boundary. Keep high moving inward only on a 2.

How this fits the two-pointer family

This is a three-way version of the quicksort partition step, and it belongs to the broader two-pointer toolkit. Once you see one pointer scanning while boundary pointers close in, you notice the shape everywhere. I broke that idea down in Two Pointers: The Pattern Inside Sorted Array Problems, and the partition mindset here extends it directly. A related variant is the fast-and-slow setup in Detect a Cycle in a Linked List, the same "let the pointers carry the invariant" idea in a different disguise.

What to practice next

Start with Sort Colors, LeetCode 75, in one pass. Then Move Zeroes, LeetCode 283, a gentler two-way partition with one boundary pointer and one scanner. After that, the quicksort partition step and Quickselect, where the three-way idea handles duplicate pivots efficiently. More pattern breakdowns live on the Levelop blog, and the problem came out of the two-pointer track on Levelop.