Dutch National Flag Problem in Java

Title: Dutch National Flag Problem in Java

The Dutch National Flag problem is a classic sorting challenge introduced by Edsger Dijkstra. Given an array that contains only three distinct values (typically 0, 1, and 2), the task is to rearrange the elements so that all 0s come first, followed by all 1s, and finally all 2s. In this guide, we’ll explore how to solve this problem in Java using an elegant three-pointer approach that runs in linear time and does the work in place.

By the end of this tutorial, you’ll understand the algorithm step by step, see the full Java program, trace it on a concrete input, review common mistakes, and practice interview follow-ups that build directly on the idea.

Understanding the Problem

You are given an array of integers where each element is 0, 1, or 2. The goal is to sort the array in a single pass without using any extra array and without calling a general-purpose sort. The name comes from the Dutch flag, which has three horizontal stripes of red, white, and blue; the sorted array mirrors that layout.

For example, if the input is:

int[] arr = {2, 0, 1, 2, 1, 0, 0, 2, 1};

Then the expected output is:

int[] sorted = {0, 0, 0, 1, 1, 1, 2, 2, 2};

A naive two-pass counting solution works, but the interesting version solves it in one pass with constant extra memory using three pointers. That is what we will build.

Approach: The Three-Pointer Technique

We maintain three indices that partition the array into four regions: a 0s region on the left, a 1s region in the middle, an unknown region yet to be examined, and a 2s region on the right. The pointers are called low, mid, and high.

Here are the steps:

1. Initialize low = 0, mid = 0, and high = arr.length - 1.
2. While mid <= high, inspect the element at arr[mid].
3. If arr[mid] == 0, swap it with arr[low], then increment both low and mid.
4. If arr[mid] == 1, it is already in the correct middle region, so just increment mid.
5. If arr[mid] == 2, swap it with arr[high] and decrement high; do NOT increment mid because the swapped-in value has not been examined yet.
6. Stop when mid crosses high; the array is now sorted in place.

Java Program for the Dutch National Flag Problem

Here is the complete, runnable Java program implementing the three-pointer algorithm:

import java.util.Arrays;

public class DutchNationalFlag {

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

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

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

    public static void main(String[] args) {
        int[] arr = {2, 0, 1, 2, 1, 0, 0, 2, 1};
        sort(arr);
        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

Explanation of the Program

The sort method takes an array of int and sorts it in place. We first set up the three indices: low marks the next slot where a 0 should go, mid is the scanner that walks through the unknown region, and high marks the next slot where a 2 should go.

The loop continues as long as mid has not passed high. On each pass we look at arr[mid] and take one of three actions. If the value is 0, we push it to the left region by swapping with arr[low], then advance both pointers. If the value is 1, it is already where it needs to be, so we just advance mid. If the value is 2, we push it to the right region by swapping with arr[high] and decrementing high; we leave mid alone because the value just swapped in from the right has not been classified yet.

The helper swap method is a standard three-line in-place swap. The main method constructs a sample array, calls sort, and prints the result using Arrays.toString.

Step-by-Step Trace

Let’s trace the algorithm on the input [2, 0, 2, 1, 1, 0]. The expected sorted output is [0, 0, 1, 1, 2, 2]. Each row shows one iteration of the while loop.

At the end of each iteration the invariant holds: arr[0..low-1] contains only 0s, arr[low..mid-1] contains only 1s, and arr[high+1..end] contains only 2s. When mid crosses high, the unknown region is empty and the array is fully sorted.

Examples

Example 1: Mixed Input with Interleaving

An input where 0s, 1s, and 2s are interleaved.

int[] arr = {0, 1, 2, 1, 0, 2};
sort(arr);
System.out.println(Arrays.toString(arr));
// Output: [0, 0, 1, 1, 2, 2]

Example 2: Mostly Twos at the Front

An input where the larger values appear early, forcing many right-side swaps.

int[] arr = {2, 2, 2, 1, 1, 0};
sort(arr);
System.out.println(Arrays.toString(arr));
// Output: [0, 1, 1, 2, 2, 2]

Example 3: Single-Element Array

The algorithm handles a one-element array correctly without entering the loop body.

int[] arr = {1};
sort(arr);
System.out.println(Arrays.toString(arr));
// Output: [1]

Common Mistakes to Avoid

Even though the algorithm is short, there are a few specific traps that trip up learners. Here are the ones to watch for:

• Advancing mid after swapping a 2 – the swap pulls in an unknown value from the right, so moving mid would skip examining it. Only decrement high; leave mid where it is.
• Using mid < high instead of mid <= high – the final element in the unknown region never gets inspected, so a trailing 0 or 2 can end up in the wrong place. The loop condition must be mid <= high.
• Initializing high = arr.length – this points one past the last valid index and causes an ArrayIndexOutOfBoundsException on the first 2. Initialize high = arr.length - 1.
• Skipping the swap when arr[mid] == arr[low] – some learners add an unnecessary check to avoid self-swaps. The algorithm is correct and clearer when the swap always runs; the extra branch adds no measurable savings.
• Returning a new array instead of sorting in place – the whole point of this approach is O(1) extra memory. Allocating a result array defeats the design and silently fails tests that assert in-place mutation.

Edge Cases to Test

Before you declare the solution complete, walk through these inputs. They cover the boundary conditions interviewers probe for:

• Empty array
• Single-element array
• Array of all identical values (all 0s, all 1s, or all 2s)
• Already sorted input
• Reverse-sorted input (2s first, then 1s, then 0s)
• Two-element arrays in every ordering
• An input containing a value outside {0, 1, 2}
• Null array reference

Additional Considerations

The three-pointer approach runs in O(n) time because each element is examined at most twice: once when mid advances past it, and possibly once when it is swapped in from the right boundary. It uses O(1) auxiliary memory since the sort happens in place with just three index variables and a temporary used by swap.

Compare this with a counting-sort approach, which also runs in O(n) time but requires two passes over the array: one to count the frequencies of 0, 1, and 2, and a second to overwrite the array. Both solutions are linear, but the three-pointer version is a single pass and is the one interviewers expect to see.

If your input might contain values outside {0, 1, 2}, add a guard that throws IllegalArgumentException at the top of the loop body. Silently producing a corrupt ordering is far worse than failing fast at the call site.

Interview Follow-up Questions

The Dutch National Flag problem is a jumping-off point for many related interview questions. Expect to be asked some of the following:

• How would you adapt the algorithm to sort an array of k distinct values instead of three? – for general k, counting sort gives O(n + k) and is simpler; three pointers do not generalize cleanly beyond three regions.
• Can you partition an array of arbitrary integers around a pivot in a single pass? – yes, replace the equality checks with comparisons against the pivot; this is the core step of three-way quicksort.
• What if the array is read-only? – you cannot sort in place, so return a new array; a counting pass plus a reconstruction pass gives O(n) time with O(n) extra memory.
• How would you make the sort stable? – the three-pointer approach is not stable because swaps reorder equal elements; use counting sort with explicit output positions to preserve relative order.
• How would you parallelize this across multiple threads for a very large array? – partition the array into chunks, run the three-pointer sort on each chunk, then merge the three regions from each chunk; the merge step is O(n) with careful index bookkeeping.

Conclusion

The Dutch National Flag problem is a beautiful example of how three well-chosen pointers can replace a counting pass with an elegant single-pass, in-place sort. Once you internalize the invariant that each region grows from its boundary, the code almost writes itself and generalizes to three-way partitioning in quicksort.

Try adapting the program to track the number of swaps, or to work on an array of characters 'R', 'W', 'B' instead of integers. These small variations cement the pattern and prepare you for interview follow-ups.

You can learn more about array algorithms here: Arrays.