Sort Colors: The Dutch National Flag Algorithm

LeetCode Sort Colors (problem 75) gives you an array where every element is 0, 1, or 2. These represent red, white, and blue. Your job: sort the array in-place so all the 0s come first, then the 1s, then the 2s. You cannot use a library sort.

This is the classic Dutch national flag problem, originally proposed by Edsger Dijkstra. It is a three pointer partition, and once you see the pattern, it clicks forever.

The problem

Given nums = [2, 0, 2, 1, 1, 0], produce [0, 0, 1, 1, 2, 2]. The values 0, 1, and 2 represent colors, but really this is about partitioning an array into three groups in a single pass.

The follow-up question on LeetCode says: "Could you come up with a one-pass algorithm using only constant extra space?" That is exactly what the Dutch national flag algorithm does.

Approach 1: Counting (two-pass)

The simplest approach: count how many 0s, 1s, and 2s exist, then overwrite the array.

def sort_colors(nums: list[int]) -> None:
    counts = [0, 0, 0]
    for num in nums:
        counts[num] += 1

    i = 0
    for color in range(3):
        for _ in range(counts[color]):
            nums[i] = color
            i += 1

This works. O(n) time, O(1) space. But it requires two passes over the array: one to count, one to write. The interviewer will ask if you can do it in a single pass.

Approach 2: Dutch national flag (one pass, three pointers)

Here is the idea. Maintain three pointers: lo, mid, and hi. They divide the array into four regions:

• Everything before lo is 0 (red)
• Everything from lo to mid - 1 is 1 (white)
• Everything from mid to hi is unprocessed
• Everything after hi is 2 (blue)

The mid pointer scans through the unprocessed region. At each step, look at nums[mid]:

• If it is 0: swap it with nums[lo], then advance both lo and mid
• If it is 1: it is already in the right zone, just advance mid
• If it is 2: swap it with nums[hi], then decrement hi (but do NOT advance mid, because the swapped-in value has not been examined yet)

You stop when mid passes hi. At that point, every element has been classified.

def sort_colors(nums: list[int]) -> None:
    lo, mid, hi = 0, 0, 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

That is the entire solution. One while loop, three branches, no extra data structures.

Visual walkthrough

Let's trace through nums = [2, 0, 2, 1, 1, 0] step by step. Watch how lo, mid, and hi carve the array into sorted regions.

Notice the pattern: reds accumulate on the left, blues on the right, and whites fill the middle. Each element gets swapped at most twice. The whole thing finishes in one pass.

Why the pointer logic works

Think of it this way. The three pointers maintain an invariant at every step:

• nums[0..lo-1] are all 0
• nums[lo..mid-1] are all 1
• nums[hi+1..n-1] are all 2
• nums[mid..hi] are unexamined

When mid finds a 0, it belongs in the red zone. So you swap it to lo and expand both the red zone (lo++) and the examined zone (mid++). The value that comes back from lo must be 1 (because it was between lo and mid-1), so it is safe to skip it.

When mid finds a 2, it belongs in the blue zone. You swap it to hi and shrink the blue zone boundary (hi--). But the value that arrives from hi is unknown, so you leave mid where it is and check it again next iteration.

When mid finds a 1, it is exactly where it should be. Just move on.

Complexity

Both are O(n) time and O(1) space. The Dutch national flag does it in a single pass, which matters when data is streaming or when the interviewer explicitly asks for one pass.

The building blocks

This problem breaks down into one core reusable brick:

Read-write pointer

The Dutch national flag algorithm is a three-way read-write pointer pattern. You have a scanning pointer (mid) that reads each element and decides where to write it by swapping with either lo or hi. The read pointer and write pointers move independently based on what value is found.

# The read-write pointer core:
# mid reads, lo and hi are write targets
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

This micro-pattern shows up in many partition problems:

• Move Zeroes (LeetCode 283) uses a read pointer and a write pointer to push all zeroes to the end while keeping other elements in order.
• Remove Duplicates from Sorted Array (LeetCode 26) uses a read pointer to scan and a write pointer to track where the next unique element goes.
• Quicksort's partition step is the two-way version of exactly this idea: one read pointer, one boundary pointer, swapping elements to the correct side of the pivot.
• 3Sum uses a fixed element plus two converging pointers, which is a related partitioning strategy on sorted data.

Once you can write a read-write pointer loop without hesitation, you can compose it into solutions for all of these.

Common mistakes

1. Advancing mid after swapping with hi. This is the most common bug. When you swap nums[mid] with nums[hi], the new value at mid has not been inspected. If you increment mid, you will skip it and end up with an unsorted result.

2. Using mid < hi instead of mid <= hi. You need the <= because when mid equals hi, there is still one unprocessed element. Using strict less-than will leave that element unclassified.

3. Forgetting that lo always trails or equals mid. Some people try to initialize lo and mid at different positions. They should both start at 0. The invariant only works if lo never gets ahead of mid.

When to reach for this pattern

Look for these signals in a problem:

• The array has exactly two or three distinct categories to sort into
• You need to partition in-place with O(1) extra space
• The problem asks for a single-pass solution
• You see the phrase "sort" combined with a small fixed set of values
• The problem is a variation on partitioning (like quicksort's partition step)

If the values are not limited to a small set, this specific algorithm does not apply. But the read-write pointer idea generalizes to many partition problems.

Related posts

• The Two Pointers Pattern - The Dutch national flag is an extension of two pointers to three. Understanding the two-pointer foundation makes this algorithm feel natural.
• Rotate Array - Another in-place array rearrangement problem where pointer manipulation replaces extra memory.

The Dutch national flag algorithm is one of those solutions that looks like a trick until you understand the invariant. Then it stops being a trick and becomes a logical consequence of maintaining three boundaries. The mid pointer asks "what are you?" and the answer determines which boundary moves.

That clarity only comes from repetition. You write the three branches from scratch. You trace through an example by hand. You do it again a few days later, then a week after that. Eventually the loop condition, the swap logic, and the pointer updates are not something you recall. They are something you reconstruct from the invariant because you understand why each line exists.