Dutch National Flag Problem (Three-Way Partition, Sort Colors)

• Dutch National Flag – an in-place partitioning algorithm that sorts an array of three distinct values into three contiguous groups in a single linear pass.
• Three pointers – low marks the end of the smallest-value region, high marks the start of the largest-value region, and mid scans the unknown portion.
• Invariant – everything before low is the smallest value, between low and mid is the middle value, mid to high is unknown, and after high is the largest value.
• Asymmetry – after swapping to low, both low and mid advance; after swapping to high, only high moves because the incoming value is unexamined.
• Complexity – O(n) time, O(1) space.

What is the Dutch National Flag problem?

The Dutch National Flag problem partitions an array of three distinct values into three contiguous groups in a single pass using three pointers. It was introduced by Edsger Dijkstra as a demonstration of three-way partitioning. In interview settings it appears as LeetCode 75 (Sort Colors) where the values are 0 (red), 1 (white), and 2 (blue).

The constraint is a single pass with O(1) extra space, which rules out both general comparison sorts and the two-pass counting approach.

package com.bank.service;

// Problem: sort [2, 0, 2, 1, 1, 0] into [0, 0, 1, 1, 2, 2]
// Constraint: single pass, O(1) space, no counting, no library sort

How does the three-pointer algorithm work?

Initialize low = 0, mid = 0, high = n - 1. The region before low holds confirmed smallest values, after high holds confirmed largest values, and mid to high is unexamined.

• Examine arr[mid]:
• If it is the smallest value (0), swap it with arr[low], advance both low and mid.
• If it is the middle value (1), just advance mid.
• If it is the largest value (2), swap it with arr[high], decrement high, do not advance mid.

Continue while mid <= high.

package com.bank.service;

import java.util.Arrays;

public class DutchNationalFlag {

    public static void partition(int[] arr) {
        int low = 0, mid = 0, high = arr.length - 1;

        while (mid <= high) {
            if (arr[mid] == 0) {
                swap(arr, low++, mid++);
            } else if (arr[mid] == 1) {
                mid++;
            } else {
                swap(arr, mid, high--);
            }
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    public static void main(String[] args) {
        int[] risk = {2, 0, 2, 1, 1, 0};
        System.out.println("Before: " + Arrays.toString(risk));
        partition(risk);
        System.out.println("After:  " + Arrays.toString(risk));
    }
}

Before: [2, 0, 2, 1, 1, 0]
After:  [0, 0, 1, 1, 2, 2]

Why is the pointer asymmetry the crux?

When you swap a zero to the low boundary, the element that comes back to mid was in the low region, which has already been scanned. It is a confirmed one (or the same position). So advancing mid is safe.

When you swap a two to the high boundary, the element that comes back from high is from the unexamined region. It could be a zero, one, or two. Advancing mid would skip it, potentially leaving a zero stranded among the ones. So mid must stay and re-examine the new arrival.

package com.bank.service;

import java.util.Arrays;

public class AsymmetryProof {
    public static void main(String[] args) {
        // Without the asymmetry rule, this case breaks
        int[] arr = {2, 0, 1};
        // Step 1: mid=0 sees 2, swap(0,2) -> [1,0,2], high=1
        // If we wrongly advance mid to 1:
        //   mid=1 sees 0, swap(0,1) -> [0,1,2], done, but by luck
        // Now try [2, 2, 0]:
        // Step 1: mid=0 sees 2, swap(0,2) -> [0,2,2], high=1
        // If we wrongly advance mid to 1:
        //   mid=1 sees 2, swap(1,1) -> [0,2,2], high=0
        //   mid > high -> done, but [0,2,2] is correct by luck
        // Try [2, 0, 0, 2, 1]:
        // Correct behavior needs mid to stay after high-swap
        int[] test = {2, 0, 0, 2, 1};
        DutchNationalFlag.partition(test);
        System.out.println(Arrays.toString(test));
    }
}

[0, 0, 1, 2, 2]

How is this different from counting sort?

The counting approach scans once to count each value, then overwrites. It is also O(n) but takes two passes and destroys original object identity.

| Feature | Dutch National Flag | Counting Sort |
|---|---|---|
| Passes | Single | Two (count + overwrite) |
| Moves objects | Yes, swaps in place | No, overwrites |
| Works on objects | Yes | Only primitive values |
| Preserves identity | Yes | No |
| Extra space | O(1) three pointers | O(1) three counters |

package com.bank.service;

import java.util.Arrays;

public class CountingApproach {
    public static void sort012(int[] arr) {
        int c0 = 0, c1 = 0, c2 = 0;
        for (int v : arr) {
            if (v == 0) c0++;
            else if (v == 1) c1++;
            else c2++;
        }
        int i = 0;
        while (c0-- > 0) arr[i++] = 0;
        while (c1-- > 0) arr[i++] = 1;
        while (c2-- > 0) arr[i++] = 2;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 0, 1, 2, 0};
        sort012(arr);
        System.out.println(Arrays.toString(arr));
    }
}

[0, 0, 1, 1, 2, 2]

What are the edge cases?

• All same value: [1,1,1] makes no swaps; mid advances through the whole array.
• Already sorted: [0,0,1,2,2] no unnecessary swaps.
• Reverse sorted: [2,2,1,0,0] maximum swaps.
• Two values only: [0,2,0,2] works because the algorithm handles any subset of three values.
• Empty or single: loop condition mid <= high handles both.

package com.bank.service;

import java.util.Arrays;

public class DNFEdgeCases {
    public static void main(String[] args) {
        int[][] tests = {{1,1,1}, {0,0,1,2,2}, {2,2,1,0,0}, {}, {0}};
        for (int[] t : tests) {
            DutchNationalFlag.partition(t);
            System.out.println(Arrays.toString(t));
        }
    }
}

[1, 1, 1]
[0, 0, 1, 2, 2]
[0, 0, 1, 2, 2]
[]
[0]

What are common mistakes?

The two most common bugs:

1. Advancing `mid` after a high-swap, which skips the unexamined value.
2. Using `mid < high` instead of `mid <= high`, which fails to classify the last unknown element.

// WRONG: mid advances after high-swap
if (arr[mid] == 2) {
    swap(arr, mid, high--);
    mid++; // BUG
}

// CORRECT: mid stays
if (arr[mid] == 2) {
    swap(arr, mid, high--);
}

How does this relate to three-way quicksort?

The Dutch National Flag partition is exactly the partition step in three-way quicksort (fat partition quicksort). The pivot plays the role of the middle value. Elements less than the pivot go left, equal go middle, greater go right. This handles arrays with many duplicates efficiently, avoiding the O(n squared) worst case of standard quicksort on all-equal input.

package com.bank.service;

public class ThreeWayQuickSort {
    public static void sort(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = arr[lo];
        int low = lo, mid = lo, high = hi;
        while (mid <= high) {
            if (arr[mid] < pivot) swap(arr, low++, mid++);
            else if (arr[mid] > pivot) swap(arr, mid, high--);
            else mid++;
        }
        sort(arr, lo, low - 1);
        sort(arr, high + 1, hi);
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

What about the banking domain application?

At the National Bank of India, the risk engine tags each pending settlement as low (0), medium (1), or high (2) risk. The operations desk needs the queue reordered so all low-risk settlements come first, then medium, then high, letting them clear safe ones quickly and scrutinize the risky tail. The queue is large, so a second array is wasteful, and the single-pass three-pointer partition reorganizes it in place.

package com.bank.service;

import java.util.Arrays;

public class RiskQueueOrganizer {
    public static void main(String[] args) {
        int[] settlements = {2, 1, 0, 2, 1, 0, 1, 2, 0};
        System.out.println("Before: " + Arrays.toString(settlements));
        DutchNationalFlag.partition(settlements);
        System.out.println("After:  " + Arrays.toString(settlements));
    }
}

Before: [2, 1, 0, 2, 1, 0, 1, 2, 0]
After:  [0, 0, 0, 1, 1, 1, 2, 2, 2]

What are common interview follow-up questions?

• Can you do it without the counting approach? (Yes, three pointers.)
• Why does mid not advance after a high-swap? (The incoming value is unexamined.)
• Is this stable? (No, relative order within a group is not preserved.)
• What if there are four values? (Three pointers do not extend directly; consider multiple passes or a different approach.)
• How does this connect to quicksort? (It is the three-way partition step.)