Sort Colors (Dutch National Flag): Three Pointers for 0s, 1s, 2s

• Sort Colors – LeetCode problem 75 that asks you to sort an array containing only 0, 1, and 2 representing red, white, and blue.
• Dutch National Flag – the algorithm that solves this in a single pass using three pointers: low, mid, and high.
• Invariant – elements before low are 0, elements from low to mid - 1 are 1, elements after high are 2, and mid to high is unknown.
• Key asymmetry – after swapping a 2 to the high end, mid does not advance because the incoming value is unexamined.
• Complexity – O(n) time and O(1) space, which is optimal for three-valued arrays.

What is the Sort Colors problem?

Sort Colors is LeetCode problem 75. You are given an array where each element is 0 (red), 1 (white), or 2 (blue). You must sort the array in place so all 0s come first, then all 1s, then all 2s. The constraint is to do it in a single pass without using a library sort.

This is the Dutch National Flag problem in disguise. The canonical solution uses three pointers.

package com.bank.service;

// LeetCode 75: Sort Colors
// Input:  [2, 0, 2, 1, 1, 0]
// Output: [0, 0, 1, 1, 2, 2]

How does the three-pointer solution work?

Initialize low = 0, mid = 0, high = n - 1. The loop runs while mid <= high. There are three cases based on arr[mid].

If arr[mid] == 0, swap arr[low] and arr[mid], then increment both low and mid. The value coming from low is already processed (it is either a 1 or the same position). If arr[mid] == 1, it belongs in the middle, so just increment mid. If arr[mid] == 2, swap arr[mid] and arr[high], then decrement high only. Do not increment mid because the value swapped in from high is unexamined.

package com.bank.service;

public class SortColors {

    public void sortColors(int[] nums) {
        int low = 0;
        int mid = 0;
        int high = nums.length - 1;

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

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

Why does mid stay put after a two-swap?

The value swapped in from the high end has never been seen by mid. It could be 0, 1, or 2. If you advanced mid, you would skip examining it, potentially leaving a 0 stranded among the 1s. When you swap a 0 to low, the value coming from low was already in the scanned region (it must be a 1), so advancing mid is safe.

package com.bank.service;

import java.util.Arrays;

public class AsymmetryDemo {
    public static void main(String[] args) {
        int[] colors = {2, 0, 1};
        System.out.println("Before: " + Arrays.toString(colors));
        // mid=0 sees 2: swap(0,2) -> [1,0,2] high=1, mid stays at 0
        // mid=0 sees 1: advance mid to 1
        // mid=1 sees 0: swap(0,1) -> [0,1,2] low=1 mid=2
        // mid > high -> done
        new SortColors().sortColors(colors);
        System.out.println("After:  " + Arrays.toString(colors));
    }
}

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

How is this different from counting sort?

Counting sort counts how many 0s, 1s, and 2s exist, then overwrites the array. It is also O(n) but takes two passes and overwrites values rather than moving them.

| Feature | Dutch National Flag | Counting Sort |
|---|---|---|
| Passes | One | Two (count + write) |
| Moves objects | Yes (swaps in place) | No (overwrites) |
| Works on objects | Yes | No, only primitives |
| Extra space | O(1) three pointers | O(1) three counters |

package com.bank.service;

import java.util.Arrays;

public class CountingAlternative {
    public static void sortByCounting(int[] nums) {
        int c0 = 0, c1 = 0, c2 = 0;
        for (int n : nums) {
            if (n == 0) c0++;
            else if (n == 1) c1++;
            else c2++;
        }
        int i = 0;
        while (c0-- > 0) nums[i++] = 0;
        while (c1-- > 0) nums[i++] = 1;
        while (c2-- > 0) nums[i++] = 2;
    }

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

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

What are the edge cases?

Edge cases that interviewers test:

• Empty array: the loop does not execute because mid > high.
• Single element: one iteration classifies it and the loop ends.
• All same value: [1,1,1] advances mid through the whole array with no swaps.
• Already sorted: [0,0,1,2,2] places everything correctly with no unnecessary swaps.
• Two values only: [0,2,0,2] works because the three-pointer handles any subset of values.

package com.bank.service;

import java.util.Arrays;

public class EdgeCases {
    public static void main(String[] args) {
        SortColors solver = new SortColors();
        int[][] tests = {{}, {2}, {1,1,1}, {0,0,1,2,2}, {0,2,0,2}};
        for (int[] t : tests) {
            solver.sortColors(t);
            System.out.println(Arrays.toString(t));
        }
    }
}

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

What are common mistakes?

The two most common bugs in interviews:

// WRONG: advancing mid after a two-swap
if (nums[mid] == 2) {
    swap(nums, mid, high);
    high--;
    mid++;  // BUG: skips unexamined value from high
}

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

The second common mistake is using mid < high instead of mid <= high. When mid == high, the element at that position is still in the unknown region and must be classified.

What about the banking domain application?

At the National Bank of India, the fraud detection system tags each incoming transaction with a risk tier: 0 for low risk, 1 for medium, 2 for high. The operations desk needs the live queue grouped by tier so reviewers process low-risk transactions quickly and escalate high-risk ones. The Dutch National Flag sorts the shared queue array in place without copying, which is important when the queue holds full transaction objects.

package com.bank.service;

import java.math.BigDecimal;
import java.util.Arrays;

public class FraudQueueSorter {
    public static void main(String[] args) {
        // Risk tiers for today's transactions
        int[] riskTiers = {2, 1, 0, 2, 1, 0, 1, 2, 0};
        System.out.println("Before: " + Arrays.toString(riskTiers));
        new SortColors().sortColors(riskTiers);
        System.out.println("After:  " + Arrays.toString(riskTiers));
        // Reviewers see: all low-risk first, then medium, then high
    }
}

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 solve it without counting? (Yes, three pointers.)
• What if there are four values? (Three pointers do not extend directly; use multiple passes or a different approach.)
• Is this stable? (No, relative order within a group is not preserved. Use counting sort for stability.)
• How does this relate to quicksort? (It is the three-way partition step used in fat-pivot quicksort.)
• What is the maximum number of swaps? (At most n, since each swap places at least one value in its final position.)