Sort 0s, 1s, and 2s in One Pass (Dutch National Flag)

• Dutch National Flag – an algorithm that sorts an array containing only three distinct values (0, 1, 2) in a single linear pass.
• Three pointers – low marks the boundary of the zeros region, high marks the boundary of the twos region, and mid scans the unknown portion.
• Invariant – everything before low is a confirmed zero, everything between low and mid is a confirmed one, and everything after high is a confirmed two.
• Swap rules – a zero at mid swaps with low and advances both; a two at mid swaps with high and decrements only high; a one at mid just advances mid.
• Asymmetry – after a two-swap mid stays because the incoming value from high is unexamined; after a zero-swap mid advances because the incoming value from low is already processed.

What is the Dutch National Flag problem?

The Dutch National Flag problem asks you to sort an array that contains only three distinct values, conventionally zero, one, and two, into three contiguous groups in a single pass. The name comes from the Dutch flag, which has three horizontal stripes of red, white, and blue. Edsger Dijkstra originally posed this problem to illustrate the three-way partitioning technique.

In interview settings this appears as LeetCode 75 (Sort Colors), and the interviewer expects the three-pointer single-pass solution rather than a general sort or a counting approach.

package com.bank.service;

// Problem: sort an array of 0s, 1s, and 2s in one pass
// Input:  [2, 0, 2, 1, 1, 0]
// Output: [0, 0, 1, 1, 2, 2]

Why does this problem matter?

A general comparison sort runs in O(n log n) time, but when the array has only three distinct values, you can exploit that constraint for a linear-time single-pass solution. The Dutch National Flag algorithm achieves O(n) time and O(1) space, which is optimal for this case.

In banking, risk classification often groups items into three tiers. At the National Bank of India, Rajesh's transaction review queue tags every transaction as low (0), medium (1), or high (2) risk. Grouping them in place in one pass lets reviewers clear safe items fast and focus on high-risk ones.

package com.bank.model;

public class RiskTransaction {
    private String transactionId;
    private int riskLevel; // 0 = low, 1 = medium, 2 = high

    public RiskTransaction(String transactionId, int riskLevel) {
        this.transactionId = transactionId;
        this.riskLevel = riskLevel;
    }

    public int getRiskLevel() { return riskLevel; }
    public String getTransactionId() { return transactionId; }
}

How does the three-pointer algorithm work internally?

You keep three indices. low starts at 0 and marks where the next zero belongs. high starts at n - 1 and marks where the next two belongs. mid starts at 0 and scans the array. The invariant is:

• Everything before low is a confirmed zero.
• Everything from low to mid - 1 is a confirmed one.
• Everything from mid to high is unknown.
• Everything after high is a confirmed two.

You loop while mid <= high. At each step you inspect arr[mid]:

• If it is 0, swap arr[low] and arr[mid], then increment both low and mid.
• If it is 1, just increment mid.
• If it is 2, swap arr[mid] and arr[high], then decrement high only.

package com.bank.service;

public class RiskSorter {

    public static void sortRiskLevels(int[] risk) {
        int low = 0;
        int mid = 0;
        int high = risk.length - 1;

        while (mid <= high) {
            if (risk[mid] == 0) {
                swap(risk, low, mid);
                low++;
                mid++;
            } else if (risk[mid] == 1) {
                mid++;
            } else {
                swap(risk, mid, high);
                high--;
                // mid does NOT advance here
            }
        }
    }

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

Why does mid NOT advance after a two-swap?

This asymmetry is the heart of the algorithm and the most common mistake in interviews. When you swap a zero from mid to low, the value that comes back to mid was sitting in the low region. That region has already been scanned by mid, so the incoming value is either a zero that is already at its final place or a one that belongs in the middle. Either way it is safe to advance mid.

When you swap a two from mid to high, the value that comes back from high has never been examined. It could be a zero, a one, or another two. If you advance mid without looking at it, you could leave a zero stranded in the ones region. So you must re-examine mid on the next iteration.

package com.bank.service;

import java.util.Arrays;

public class SwapAsymmetryDemo {
    public static void main(String[] args) {
        // Example showing why mid must not advance after a two-swap
        int[] risk = {2, 0, 1};
        System.out.println("Before: " + Arrays.toString(risk));

        // Step 1: mid=0, arr[0]=2, swap with high=2 -> [1, 0, 2], high=1
        // mid stays at 0, now arr[0]=1 which is unknown from high
        // Step 2: mid=0, arr[0]=1, just advance mid -> mid=1
        // Step 3: mid=1, arr[1]=0, swap with low=0 -> [0, 1, 2], done

        RiskSorter.sortRiskLevels(risk);
        System.out.println("After:  " + Arrays.toString(risk));
    }
}

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

How is this different from the counting sort approach?

The counting approach scans the array once to count zeros, ones, and twos, then overwrites the array in a second pass. It is also O(n) time and O(1) space, but it takes two passes and overwrites values rather than moving them.

| Feature | Dutch National Flag | Counting Sort |
|---|---|---|
| Passes | Single pass | Two passes (count + overwrite) |
| Moves elements | Yes, swaps in place | No, overwrites with counts |
| Works on objects | Yes, moves actual objects | No, only works on primitive values |
| Extra space | O(1) three pointers | O(1) three counters |
| Preserves identity | Yes | No (overwrites) |

The Dutch National Flag wins when you must do a true single pass or when the elements are objects classified into three groups where you want to move them, not overwrite them.

package com.bank.service;

import java.util.Arrays;

public class CountingSortAlternative {
    // Two-pass counting approach for comparison
    public static void sortByCounting(int[] risk) {
        int count0 = 0, count1 = 0, count2 = 0;
        for (int r : risk) {
            if (r == 0) count0++;
            else if (r == 1) count1++;
            else count2++;
        }
        int idx = 0;
        while (count0-- > 0) risk[idx++] = 0;
        while (count1-- > 0) risk[idx++] = 1;
        while (count2-- > 0) risk[idx++] = 2;
    }

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

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

What are the edge cases?

Several edge cases are worth testing in an interview to show thoroughness.

• All same value: [1, 1, 1] should remain unchanged. The algorithm handles this because mid advances through all ones without any swaps.
• Already sorted: [0, 0, 1, 1, 2, 2] should remain unchanged. No swaps occur because each value is already in its correct region.
• Reverse sorted: [2, 2, 1, 1, 0, 0] triggers the maximum number of swaps.
• Single element: [0] or [2] works because mid <= high holds for one iteration.
• Empty array: mid > high immediately, so the loop does not execute.

package com.bank.service;

import java.util.Arrays;

public class EdgeCaseDemo {
    public static void main(String[] args) {
        int[][] cases = {
            {1, 1, 1},           // all same
            {0, 0, 1, 1, 2, 2}, // already sorted
            {2, 2, 1, 1, 0, 0}, // reverse sorted
            {0},                 // single element
            {}                   // empty array
        };
        for (int[] c : cases) {
            RiskSorter.sortRiskLevels(c);
            System.out.println(Arrays.toString(c));
        }
    }
}

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

What are common mistakes?

The most frequent bug is advancing mid after a two-swap. This skips the unexamined value that arrived from the high end.

// WRONG: advancing mid after a two-swap
if (risk[mid] == 2) {
    swap(risk, mid, high);
    high--;
    mid++; // BUG: the value swapped in from high is unexamined
}

// CORRECT: mid stays after a two-swap
if (risk[mid] == 2) {
    swap(risk, mid, high);
    high--;
    // mid does NOT advance
}

Another common mistake is using mid < high instead of mid <= high as the loop condition. When mid == high, the element at that position has not been classified yet, so it must still be examined.

How does this relate to three-way quicksort?

The Dutch National Flag partition is exactly the partition step in three-way quicksort (also called fat partition quicksort). In three-way quicksort, the pivot plays the role of the "one" value. Elements smaller than the pivot go left, elements equal go middle, and elements greater go right. This handles arrays with many duplicate keys efficiently, avoiding the O(n squared) worst case that standard quicksort hits with 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 thread safety and concurrency?

The algorithm mutates the array in place, so it is not thread-safe by default. If multiple threads read the risk queue while sorting is in progress, they may see a partially sorted state. In the National Bank of India's fraud review tool, Rajesh wraps the sort call in a synchronized block or uses a read-write lock so that readers wait until sorting completes.

package com.bank.service;

import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class ThreadSafeRiskSorter {
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final int[] riskQueue;

    public ThreadSafeRiskSorter(int[] riskQueue) {
        this.riskQueue = riskQueue;
    }

    public void sortRiskLevels() {
        lock.writeLock().lock();
        try {
            RiskSorter.sortRiskLevels(riskQueue);
        } finally {
            lock.writeLock().unlock();
        }
    }
}

What are common interview follow-up questions?

• Can you do it in one pass without extra space? (Yes, Dutch National Flag.)
• What if there are four distinct values instead of three? Can the three-pointer approach extend? (Not directly. You would need a different partition strategy or multiple passes.)
• What is the maximum number of swaps? (At most n swaps, since each swap places at least one element in its final position.)
• How does this relate to quicksort? (It is the three-way partition step used in fat-pivot quicksort.)
• Can you sort the array stably? (The Dutch National Flag does not preserve relative order within a group. For stability, counting sort is preferred.)