Dutch National Flag: Patterns

March 2026 · 18 min read

The three-way partition from the Dutch National Flag problem is not limited to sorting 0s, 1s, and 2s. The same pointer technique appears whenever you need to classify elements into three groups in a single pass. This post covers the most important patterns built on that idea.

Pattern 1: Three-Way Quicksort Partition

Standard quicksort picks a pivot and partitions the array into two groups: elements less than the pivot and elements greater than the pivot. When the array contains many duplicate keys, this leads to poor performance because duplicates end up on one side and must be re-partitioned in subsequent recursive calls.

The fix is a three-way partition: elements less than the pivot go left, elements equal to the pivot stay in the middle, and elements greater go right. The middle group is already in its final position and is excluded from further recursion.

How It Maps to DNF

Replace the three categories (0, 1, 2) with comparisons against the pivot:

• Less than pivot plays the role of 0 (goes to the left region)
• Equal to pivot plays the role of 1 (stays in the middle)
• Greater than pivot plays the role of 2 (goes to the right region)

Step-Through Animation

Array: [4, 9, 4, 2, 7, 4, 1, 4, 8], pivot = 4. Watch elements less than 4 (green) move left, equal to 4 (gray) collect in the middle, and greater than 4 (red) move right.

C++ Implementation

#include <vector>
#include <algorithm>

// Three-way partition around pivot value.
// Returns [eqLow, eqHigh]: indices bounding the equal region.
std::pair<int,int> threeWayPartition(
        std::vector<int>& a, int lo, int hi, int pivot) {
    int low = lo, mid = lo, high = hi;
    while (mid <= high) {
        if (a[mid] < pivot) {
            std::swap(a[low], a[mid]);
            ++low; ++mid;
        } else if (a[mid] == pivot) {
            ++mid;
        } else {
            std::swap(a[mid], a[high]);
            --high;
        }
    }
    return {low, high};
}

// Quicksort using three-way partition.
void quickSort3Way(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[lo + (hi - lo) / 2];
    auto [eqLo, eqHi] = threeWayPartition(a, lo, hi, pivot);
    quickSort3Way(a, lo, eqLo - 1);
    quickSort3Way(a, eqHi + 1, hi);
}

Complexity Comparison

Pattern 2: Segregate Negatives, Zeros, and Positives

Given an array of integers, rearrange it so that all negative numbers come first, then all zeros, then all positive numbers. The relative order within each group does not need to be preserved (unstable partition).

This maps directly to the DNF pattern:

• Negative plays the role of 0 (left region)
• Zero plays the role of 1 (middle region)
• Positive plays the role of 2 (right region)

Step-Through Animation

Array: [3, -2, 0, -7, 5, 0, -1, 4]. Negatives (green) go left, zeros (gray) stay in the middle, positives (red) go right.

C++ Implementation

#include <vector>
#include <algorithm>

void segregate(std::vector<int>& a) {
    int low = 0, mid = 0, high = (int)a.size() - 1;
    while (mid <= high) {
        if (a[mid] < 0) {
            std::swap(a[low], a[mid]);
            ++low; ++mid;
        } else if (a[mid] == 0) {
            ++mid;
        } else {
            std::swap(a[mid], a[high]);
            --high;
        }
    }
}

The logic is identical to the original DNF algorithm. The only change is the condition: instead of checking for 0, 1, 2, we check the sign of the element.

Walkthrough

Pattern 3: Move All X to a Target Position

Given an array and a target value X, rearrange the array so that all occurrences of X are in a specific region (front, middle, or end) and all other elements fill the remaining positions. This is a two-way or three-way partition depending on the exact requirement.

Variant A: Move X to the End

Move all occurrences of a given value to the end of the array. This is a simplified two-pointer version of DNF (only two categories: "not X" and "X").

void moveToEnd(std::vector<int>& a, int x) {
    int low = 0, high = (int)a.size() - 1;
    while (low <= high) {
        if (a[low] != x) {
            ++low;
        } else {
            std::swap(a[low], a[high]);
            --high;
        }
    }
}

Here low scans forward and high marks the boundary of the "X region" growing from the right. When a[low] equals X, swap it to the back. When it does not, advance past it.

Variant B: Move X to the Front

Symmetric to variant A. Swap matching elements toward the beginning.

void moveToFront(std::vector<int>& a, int x) {
    int write = 0;
    for (int read = 0; read < (int)a.size(); ++read) {
        if (a[read] == x) {
            std::swap(a[write], a[read]);
            ++write;
        }
    }
}

Variant C: Three-Way with X in the Middle

Given values less than X, equal to X, and greater than X, place X in the middle. This is the full DNF pattern applied with X as the pivot.

void moveXToMiddle(std::vector<int>& a, int x) {
    int low = 0, mid = 0, high = (int)a.size() - 1;
    while (mid <= high) {
        if (a[mid] < x) {
            std::swap(a[low], a[mid]);
            ++low; ++mid;
        } else if (a[mid] == x) {
            ++mid;
        } else {
            std::swap(a[mid], a[high]);
            --high;
        }
    }
}

This is identical to the three-way quicksort partition from Pattern 1. The only difference is the caller's intent: here we want X specifically in the middle rather than partitioning for a recursive sort.

Step-Through Animation

Array: [5, 3, 3, 7, 3, 9, 1, 3], target X = 3. Move all 3s to the end.

When to Recognize the DNF Pattern

Use the three-way partition whenever a problem asks you to classify array elements into exactly two or three groups in a single pass. Look for these signals:

• The problem says "sort" or "rearrange" with only 2 or 3 distinct categories.
• The constraint mentions O(1) extra space and a single pass (or constant number of passes).
• The problem asks to "partition around a pivot" or "segregate" values.
• Quicksort variants that handle duplicate keys.

Practice Problems

Key Takeaways

• The DNF three-pointer technique generalizes to any problem that partitions elements into three groups in one pass.
• Three-way quicksort partition uses DNF to handle duplicate keys efficiently, avoiding O(n²) degradation.
• Segregating by sign (negative, zero, positive) is a direct mapping. The comparison changes but the pointer logic is identical.
• Two-way partitions (move X to end, separate even/odd) are a simplified version that only needs two pointers.
• The pattern is always: maintain sorted regions at the boundaries, shrink the unknown region in the middle, and be careful not to skip unexamined swapped-in elements.