Neel Mishra
← All Posts
DSA Series · Arrays · Dutch National Flag

Dutch National Flag Problem

March 2026 · 12 min read

Origin: Dijkstra's Problem

In 1976, Edsger W. Dijkstra posed a deceptively simple question: given an array of elements that each belong to one of three categories, can you sort them in a single pass using constant extra memory?

He named it after the Dutch national flag, which has three horizontal bands of red, white, and blue. The task is to rearrange an array of 0s, 1s, and 2s so that all 0s (red) come first, then all 1s (white), then all 2s (blue).

This became one of the most elegant examples of 3-way partitioning. The technique underpins quicksort optimizations (when many duplicate keys exist), database query processing, and appears in coding interviews as LeetCode 75: Sort Colors.

Why not just count and overwrite? A counting approach (count 0s, 1s, 2s, then fill) works but requires two passes and does not generalize to objects with satellite data. Dijkstra's approach sorts in one pass and preserves the ability to work with complex objects, not just integers.

The Problem Statement

Given an array nums containing only values 0, 1, and 2, sort it in-place so that all 0s are at the front, all 1s in the middle, and all 2s at the end. You must do this in a single pass with O(1) extra space.

Input:  [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

This is equivalent to partitioning around a pivot value of 1: elements less than 1 go left, equal to 1 stay in the middle, greater than 1 go right.

The Three-Pointer Approach

Dijkstra's solution uses three pointers to maintain four regions of the array as we scan through it:

The algorithm processes elements at mid and decides what to do based on the value:

While mid ≤ high:
  If nums[mid] == 0: swap(nums[low], nums[mid]), low++, mid++
  If nums[mid] == 1: mid++
  If nums[mid] == 2: swap(nums[mid], nums[high]), high−1

Notice: when we swap with high, we do not advance mid. The element swapped from high is unexamined, so mid must inspect it in the next iteration.

The Loop Invariant

At every iteration, the array satisfies these four conditions simultaneously:

Region 1: nums[0..low-1] contains only 0s (red)
Region 2: nums[low..mid-1] contains only 1s (white)
Region 3: nums[mid..high] is the unknown region (not yet classified)
Region 4: nums[high+1..n-1] contains only 2s (blue)

When mid crosses high, the unknown region is empty and the entire array is sorted. This invariant is what makes the algorithm correct: each operation shrinks the unknown region by at least one element while preserving the other regions.

Step-Through Animation

Walk through the algorithm on the array [2, 0, 2, 1, 1, 0]. Press Step to advance one operation at a time, or Reset to start over. Watch the three pointers and colored cells update as elements are swapped into position.

0 (Red) 1 (White) 2 (Blue) low mid high

Detailed Walkthrough

Let us trace through [2, 0, 2, 1, 1, 0] step by step. Initial state: low = 0, mid = 0, high = 5.

Step 1
nums[mid] = nums[0] = 2. Since it is 2, swap nums[0] with nums[5] and decrement high.
Array becomes [0, 0, 2, 1, 1, 2]. Pointers: low=0, mid=0, high=4.
We did not advance mid because the swapped-in element (0) still needs inspection.
Step 2
nums[mid] = nums[0] = 0. Since it is 0, swap nums[0] with nums[0] (self-swap), increment both low and mid.
Array stays [0, 0, 2, 1, 1, 2]. Pointers: low=1, mid=1, high=4.
Step 3
nums[mid] = nums[1] = 0. It is 0 again, so swap nums[1] with nums[1] (self-swap), increment both.
Array stays [0, 0, 2, 1, 1, 2]. Pointers: low=2, mid=2, high=4.
Step 4
nums[mid] = nums[2] = 2. It is 2, swap nums[2] with nums[4], decrement high.
Array becomes [0, 0, 1, 1, 2, 2]. Pointers: low=2, mid=2, high=3.
Step 5
nums[mid] = nums[2] = 1. It is 1, just advance mid.
Array stays [0, 0, 1, 1, 2, 2]. Pointers: low=2, mid=3, high=3.
Step 6
nums[mid] = nums[3] = 1. It is 1, advance mid.
Array stays [0, 0, 1, 1, 2, 2]. Pointers: low=2, mid=4, high=3.
Now mid > high, so the loop terminates. The array is sorted.

C++ Implementation

The implementation is remarkably compact. The entire logic fits in a single while loop with three branches:

#include <vector>
#include <algorithm> // std::swap

void sortColors(std::vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            std::swap(nums[low], nums[mid]);
            ++low;
            ++mid;
        } else if (nums[mid] == 1) {
            ++mid;
        } else { // nums[mid] == 2
            std::swap(nums[mid], nums[high]);
            --high;
        }
    }
}

// Example usage
int main() {
    std::vector<int> nums = {2, 0, 2, 1, 1, 0};
    sortColors(nums);
    // nums is now {0, 0, 1, 1, 2, 2}
    return 0;
}

Complexity Analysis

Each iteration of the loop either advances mid forward or moves high backward (or both via the 0-case). The unknown region [mid..high] shrinks by at least 1 each time. Since this region starts at size n and ends at 0, the total number of iterations is at most n.

MetricValueReasoning
TimeO(n)Single pass through the array
SpaceO(1)Only three integer pointers
Swaps≤ nAt most one swap per iteration
Comparisons≤ nOne comparison per iteration

Compared to a counting sort (two passes, O(n) time, O(1) space), Dijkstra's approach matches the complexity but does it in a single pass. More importantly, it generalizes to objects with satellite data where counting and overwriting is not possible.

Why Not Advance Mid on a 2-Swap?

This is the most common source of bugs. When nums[mid] == 0 and we swap with low, the value that arrives at mid from the low position has already been examined (it was in the confirmed 1-region [low..mid-1]). So it is safe to advance mid.

But when nums[mid] == 2 and we swap with high, the value that arrives at mid from the high position is from the unknown region. It could be 0, 1, or 2. We must examine it before moving on. Forgetting this causes elements to land in the wrong region.

Correctness Proof Sketch

We prove correctness by showing the loop invariant holds at initialization, is preserved by each branch, and implies the postcondition at termination.

Common Pitfalls

Extension: 4-Way Partition

The 3-way partition generalizes naturally. Suppose you have four categories (0, 1, 2, 3). You can use four pointers: a, b, c, and d. The idea is the same: maintain sorted regions at the boundaries and an unsorted middle that shrinks each step.

The approach chains two 3-way partitions, or uses a direct 4-pointer scheme:

void fourWayPartition(std::vector<int>& nums) {
    int a = 0, b = 0, c = 0;
    int d = nums.size() - 1;

    while (c <= d) {
        if (nums[c] == 0) {
            std::swap(nums[c], nums[b]);
            std::swap(nums[b], nums[a]);
            ++a; ++b; ++c;
        } else if (nums[c] == 1) {
            std::swap(nums[c], nums[b]);
            ++b; ++c;
        } else if (nums[c] == 2) {
            ++c;
        } else { // nums[c] == 3
            std::swap(nums[c], nums[d]);
            --d;
        }
    }
}

The invariant now maintains five regions instead of four. The complexity remains O(n) time and O(1) space. This pattern is useful when partitioning data into more than three buckets, for example in multi-pivot quicksort or radix-based sorting.

Partition TypePointersCategoriesPasses
2-way (standard quicksort)221
3-way (Dutch Flag)331
4-way441
k-way (general)kk1 (with care)

The Dutch National Flag pattern appears in many forms across competitive programming and interviews:

Key Takeaways