Eric Campbell 6 min read Engineering

Dutch National Flag: Three-Way Partitioning

In 1976, Edsger Dijkstra introduced the Dutch National Flag problem as a programming exercise in his book 'A Discipline of Programming.' The problem takes its name from the Netherlands flag, which...

Key Insights

  • The Dutch National Flag algorithm partitions an array into three groups in O(n) time and O(1) space using three pointers that maintain strict invariants throughout execution.
  • Understanding this algorithm unlocks significant optimizations for QuickSort when handling duplicate keys, transforming worst-case O(n²) scenarios into O(n log n) performance.
  • The key to implementing this correctly is recognizing that you only increment the mid pointer after processing elements—a subtle detail that causes most bugs.

Introduction & Problem Statement

In 1976, Edsger Dijkstra introduced the Dutch National Flag problem as a programming exercise in his book “A Discipline of Programming.” The problem takes its name from the Netherlands flag, which consists of three horizontal bands of red, white, and blue. Dijkstra asked: given an array of elements that can be classified into three categories, how do you rearrange them so all elements of the first category come before the second, which come before the third?

The core challenge is deceptively simple: partition an array into three groups (low, mid, high) in linear time with constant space. You can’t use extra arrays. You can’t sort and call it a day. You need a single pass through the data, swapping elements into their correct regions as you go.

This isn’t just an academic exercise. The algorithm appears constantly in systems programming, database internals, and as a crucial optimization for sorting algorithms. If you’ve ever wondered why QuickSort implementations handle duplicates efficiently, the Dutch National Flag algorithm is your answer.

The Three-Pointer Algorithm Explained

The algorithm uses three pointers to divide the array into four regions:

  1. [0, low-1]: Elements less than the pivot (finalized)
  2. [low, mid-1]: Elements equal to the pivot (finalized)
  3. [mid, high]: Unexplored elements
  4. [high+1, n-1]: Elements greater than the pivot (finalized)

The mid pointer scans through the array. When it encounters an element, it either swaps it to the low region, leaves it in place, or swaps it to the high region.

Here’s the basic implementation for sorting an array containing only 0s, 1s, and 2s:

def dutch_national_flag(arr):
    low = 0
    mid = 0
    high = len(arr) - 1
    
    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:  # arr[mid] == 2
            arr[high], arr[mid] = arr[mid], arr[high]
            high -= 1
            # Note: mid is NOT incremented here
    
    return arr

The critical insight is understanding why mid doesn’t increment when swapping with high. When you swap an element from the high region, you don’t know what value you just received—it could be 0, 1, or 2. You must examine it before moving on. But when swapping with low, you know you’re receiving a 1 (since everything between low and mid-1 has already been processed as a 1), so you can safely advance.

Visual Walkthrough

Let’s trace through the algorithm with the array [2, 0, 1, 2, 1, 0]:

def dutch_national_flag_instrumented(arr):
    low = 0
    mid = 0
    high = len(arr) - 1
    step = 0
    
    print(f"Initial: {arr}")
    print(f"         low={low}, mid={mid}, high={high}\n")
    
    while mid <= high:
        step += 1
        print(f"Step {step}: arr[mid]={arr[mid]}", end=" -> ")
        
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            print(f"swap with low, increment both")
            low += 1
            mid += 1
        elif arr[mid] == 1:
            print(f"leave in place, increment mid")
            mid += 1
        else:
            arr[high], arr[mid] = arr[mid], arr[high]
            print(f"swap with high, decrement high only")
            high -= 1
        
        print(f"         {arr}")
        print(f"         low={low}, mid={mid}, high={high}\n")
    
    return arr

# Trace execution
dutch_national_flag_instrumented([2, 0, 1, 2, 1, 0])

Output:

Initial: [2, 0, 1, 2, 1, 0]
         low=0, mid=0, high=5

Step 1: arr[mid]=2 -> swap with high, decrement high only
         [0, 0, 1, 2, 1, 2]
         low=0, mid=0, high=4

Step 2: arr[mid]=0 -> swap with low, increment both
         [0, 0, 1, 2, 1, 2]
         low=1, mid=1, high=4

Step 3: arr[mid]=0 -> swap with low, increment both
         [0, 0, 1, 2, 1, 2]
         low=2, mid=2, high=4

Step 4: arr[mid]=1 -> leave in place, increment mid
         [0, 0, 1, 2, 1, 2]
         low=2, mid=3, high=4

Step 5: arr[mid]=2 -> swap with high, decrement high only
         [0, 0, 1, 1, 2, 2]
         low=2, mid=3, high=3

Step 6: arr[mid]=1 -> leave in place, increment mid
         [0, 0, 1, 1, 2, 2]
         low=2, mid=4, high=3

The algorithm terminates when mid > high, meaning all elements have been classified.

Time & Space Complexity Analysis

Time Complexity: O(n)

Each iteration either increments mid or decrements high. Since mid starts at 0 and high starts at n-1, and they move toward each other, the loop executes at most n times. Every element is examined exactly once.

Space Complexity: O(1)

We use only three integer pointers regardless of input size. All swaps happen in-place.

Compare this to naive approaches:

  • Counting sort: O(n) time but O(k) space for k distinct values
  • Standard sorting: O(n log n) time, O(1) to O(n) space depending on algorithm
  • Three-pass approach (count, then place): O(n) time but requires multiple passes

The Dutch National Flag algorithm achieves optimal time and space in a single pass.

Practical Applications

QuickSort Optimization

The most impactful application is three-way partitioning in QuickSort. Standard QuickSort degrades to O(n²) when the array contains many duplicates. Three-way partitioning groups all elements equal to the pivot together, eliminating redundant comparisons:

def quicksort_three_way(arr, lo, hi):
    if lo >= hi:
        return
    
    pivot = arr[lo]
    lt = lo      # arr[lo..lt-1] < pivot
    gt = hi      # arr[gt+1..hi] > pivot
    i = lo + 1   # arr[lt..i-1] == pivot
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[gt], arr[i] = arr[i], arr[gt]
            gt -= 1
        else:
            i += 1
    
    # Recursively sort the < and > partitions
    # Elements equal to pivot are already in final position
    quicksort_three_way(arr, lo, lt - 1)
    quicksort_three_way(arr, gt + 1, hi)

def quicksort(arr):
    quicksort_three_way(arr, 0, len(arr) - 1)
    return arr

Segregating Numbers by Sign

A common interview variant asks you to arrange an array so negative numbers come first, then zeros, then positives:

def segregate_by_sign(arr):
    low, mid, high = 0, 0, len(arr) - 1
    
    while mid <= high:
        if arr[mid] < 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 0:
            mid += 1
        else:
            arr[high], arr[mid] = arr[mid], arr[high]
            high -= 1
    
    return arr

Common Variations & Extensions

Four-Way Partitioning

When you need to partition into more than three groups, you can extend the approach with additional pointers:

def four_way_partition(arr, pivot1, pivot2):
    """
    Partitions array into four regions:
    [< pivot1] [== pivot1] [between pivots] [>= pivot2]
    Assumes pivot1 < pivot2
    """
    if pivot1 >= pivot2:
        raise ValueError("pivot1 must be less than pivot2")
    
    low = 0
    mid1 = 0
    mid2 = len(arr) - 1
    high = len(arr) - 1
    
    while mid1 <= mid2:
        if arr[mid1] < pivot1:
            arr[low], arr[mid1] = arr[mid1], arr[low]
            low += 1
            mid1 += 1
        elif arr[mid1] >= pivot2:
            while mid1 < mid2 and arr[mid2] >= pivot2:
                if arr[mid2] > pivot2:
                    arr[mid2], arr[high] = arr[high], arr[mid2]
                    high -= 1
                mid2 -= 1
            arr[mid1], arr[mid2] = arr[mid2], arr[mid1]
            if arr[mid1] < pivot1:
                arr[low], arr[mid1] = arr[mid1], arr[low]
                low += 1
            mid1 += 1
            mid2 -= 1
        else:
            mid1 += 1
    
    return arr

Stability Considerations

The standard Dutch National Flag algorithm is not stable—equal elements may change their relative order. If stability matters, you’ll need O(n) extra space or accept O(n²) time with careful in-place rotations.

Interview Tips & Edge Cases

Common Mistakes:

  1. Incrementing mid after swapping with high—this skips examining the swapped element
  2. Using mid < high instead of mid <= high—misses the final element
  3. Forgetting that low and mid start at the same position

Edge Cases to Test:

  • Empty array: []
  • Single element: [1]
  • Already sorted: [0, 0, 1, 1, 2, 2]
  • Reverse sorted: [2, 2, 1, 1, 0, 0]
  • All same value: [1, 1, 1, 1]
  • Missing categories: [0, 0, 2, 2] (no 1s)

Practice Problems:

  • LeetCode 75: Sort Colors (the classic DNF problem)
  • LeetCode 324: Wiggle Sort II (uses DNF as a building block)
  • LeetCode 905: Sort Array By Parity (two-way variant)

The Dutch National Flag algorithm is one of those foundational techniques that, once internalized, makes you see partitioning problems everywhere. Master the three-pointer dance, understand the invariants, and you’ll handle these problems instinctively.

Liked this? There's more.

Every week: one practical technique, explained simply, with code you can use immediately.