Dutch National Flag Algorithm Explained — Sort 3 Values in One Pass

Most sorting problems give you a free pass to reach for Arrays.sort() and move on. But every so often you hit a constraint that makes the generic approach feel wasteful: you only have three distinct values, you can't afford extra memory, and the input could be a million elements long. This is the exact situation the Dutch National Flag algorithm was designed for — and interviewers love it precisely because it rewards people who think about constraints before they think about code.

The classic version of this problem is LeetCode 75 'Sort Colors', where the values are 0, 1, and 2 representing red, white, and blue. A naive two-pass counting sort works, but it reads the array twice. A comparison sort is O(n log n). The Dutch National Flag solves it in a single pass — O(n) time, O(1) space — by maintaining three pointers that carve the array into four live regions simultaneously as they converge.

By the end of this article you'll understand exactly why three pointers are needed (not two, not four), you'll be able to draw the invariant on a whiteboard, write the algorithm from scratch without looking anything up, spot the two bugs that trip up nearly everyone on their first attempt, and answer every follow-up an interviewer can throw at you.

What is Dutch National Flag Algorithm?

Dutch National Flag Algorithm is a core concept in DSA. Rather than starting with a dry definition, let's see it in action and understand why it exists.

// TheCodeForge — Dutch National Flag Algorithm example
// Always use meaningful names, not x or n
public class ForgeExample {
    public static void main(String[] args) {
        String topic = "Dutch National Flag Algorithm";
        System.out.println("Learning: " + topic + " 🔥");
    }
}

Frequently Asked Questions