Separate Zeros, Ones, and Twos in an Array

Title: Separate Zeros, Ones, and Twos in an Array

In this guide, you will learn how to rearrange an integer array that contains only the values 0, 1, and 2 so that all zeros come first, then all ones, then all twos. This is the classic Dutch National Flag problem, famously posed by Edsger Dijkstra, and it is a favorite interview question for probing your mastery of in-place array partitioning.

We will build a complete Java program that solves the problem in a single pass using three pointers, walk through the algorithm line by line, trace it on a fresh input, cover the common mistakes that trip learners up, and finish with interview-style follow-ups so you can turn this exercise into real preparation.

Understanding the Problem

You are given an integer array arr whose elements are drawn from the set {0, 1, 2}. You must rearrange its elements so that every 0 appears before every 1 and every 1 appears before every 2. The rearrangement should happen in place, which means you may use only a constant amount of extra memory, and the operation should run in a single pass through the array.

A naive solution would be to sort the array, which costs O(n log n) time. A slightly better counting approach would scan twice: once to count how many of each value appear, and once to overwrite the array. The optimal solution shown below runs in O(n) time and O(1) space using a single pass and three pointers.

Approach / Algorithm Steps

We use three pointers that partition the array into four regions as the scan progresses. Everything before low is a confirmed 0. Everything from low up to mid is a confirmed 1. Everything after high is a confirmed 2. The region from mid to high is still unknown and gets processed one element at a time.

1. Initialize low to 0, mid to 0, and high to arr.length - 1.
2. While mid <= high, inspect the value at arr[mid].
3. If arr[mid] is 0, swap arr[low] with arr[mid], then increment both low and mid.
4. If arr[mid] is 1, it is already in its correct middle region, so simply increment mid.
5. If arr[mid] is 2, swap arr[mid] with arr[high], then decrement high. Do not advance mid, because the newly swapped value has not been inspected yet.
6. The loop ends when mid passes high. At that point every 0 sits in the left region, every 1 in the middle, and every 2 in the right.

Java Program

The following program defines a reusable separate method and drives it from main with a sample array so you can run and verify the output immediately.

public class SeparateZerosOnesTwos {

    public static void separate(int[] arr) {
        int low = 0;
        int mid = 0;
        int high = arr.length - 1;
        while (mid <= high) {
            if (arr[mid] == 0) {
                int temp = arr[low];
                arr[low] = arr[mid];
                arr[mid] = temp;
                low++;
                mid++;
            } else if (arr[mid] == 1) {
                mid++;
            } else {
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;
                high--;
            }
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 0, 1, 2, 0, 1, 2, 0};
        System.out.print("Original array: ");
        printArray(arr);
        separate(arr);
        System.out.print("Separated array: ");
        printArray(arr);
    }
}

Explanation of the Program

The separate method accepts the array and sets up three pointers. low and mid both start at index 0, and high starts at the last index. The while loop runs as long as mid has not passed high.

Inside the loop, the first branch handles the case where arr[mid] is 0. A 0 belongs in the leftmost region, so we swap it with arr[low] and advance both pointers. We can safely advance mid here because the value coming back from arr[low] is guaranteed to be a 1, since the low to mid region is where ones live by invariant.

The second branch handles arr[mid] equal to 1. A 1 is already in its correct middle region, so we only increment mid without touching the array.

The third branch handles arr[mid] equal to 2. A 2 belongs in the rightmost region, so we swap it with arr[high] and decrement high. We deliberately do not advance mid here, because the value that just moved to arr[mid] came from the unknown region and still has to be examined.

The printArray helper walks the array once and prints each value separated by a space. The main method prints the original and the separated arrays so you can compare them side by side.

Step-by-Step Trace

Let us trace the algorithm on the input [2, 0, 1, 2, 1, 0, 1]. The table below shows one row per iteration of the while loop so you can watch each pointer move and each swap take effect.

At the end of each iteration, every element strictly before low is a 0, every element from low to mid - 1 is a 1, and every element strictly after high is a 2. That three-way invariant is what makes the algorithm correct.

Examples

The following examples show how the method behaves on inputs with different distributions of zeros, ones, and twos.

Example 1: All three values present

A balanced mix of zeros, ones, and twos is the typical case. All three branches of the loop fire multiple times.

int[] arr = {1, 0, 2, 1, 2, 0, 1, 0, 2};
separate(arr);
printArray(arr);
// Output: 0 0 0 1 1 1 2 2 2

Example 2: Only zeros and ones

When the input contains only two of the three values, the third branch never runs. The algorithm still works unchanged because the high pointer simply never swaps anything inward.

int[] arr = {1, 0, 1, 0, 1, 0};
separate(arr);
printArray(arr);
// Output: 0 0 0 1 1 1

Example 3: Already sorted

When the input is already in the desired order, every swap is either a no-op or swaps an element with itself. The algorithm still runs in a single pass and correctly leaves the array unchanged.

int[] arr = {0, 0, 1, 1, 2, 2};
separate(arr);
printArray(arr);
// Output: 0 0 1 1 2 2

Common Mistakes to Avoid

The algorithm is short, but there are a handful of mistakes that learners make again and again on this problem. Watch out for the following.

• Advancing mid after a swap with high – the value that just moved into arr[mid] came from the unknown region and may be a 2. If you increment mid, you skip inspecting it and the result ends up unsorted. Only decrement high.
• Using mid < high as the loop condition – this stops one iteration too early and leaves the final element unprocessed. The correct condition is mid <= high so the pointer at the boundary is still inspected.
• Forgetting the temporary variable in the swap – writing arr[low] = arr[mid]; arr[mid] = arr[low]; clobbers the low value before it can be stored. Use a temp variable or Java’s three-step swap.
• Swapping with low when arr[mid] is 1 – a 1 is already in its correct region, so swapping it with the boundary wastes work and can produce incorrect results if low and mid have diverged. Just increment mid.
• Initializing high to arr.length – this reads past the end of the array on the first iteration and throws ArrayIndexOutOfBoundsException. Initialize high to arr.length - 1.

Edge Cases to Test

A good interview answer walks through the following boundary inputs without being asked. Mention the first three before you start coding.

• Empty array
• Single-element array
• All elements equal to 0
• All elements equal to 1
• All elements equal to 2
• Already sorted input [0, 1, 2]
• Reverse sorted input [2, 1, 0]
• Null array reference

Additional Considerations

The time complexity is O(n), where n is the length of the array. The mid pointer only moves right and the high pointer only moves left, so between them they cover each index at most once. The space complexity is O(1) because the only extra storage is the temp variable used during each swap.

This single-pass version strictly beats the two-pass counting approach even though both are O(n). The counting approach touches each cell twice, once to count and once to overwrite, which doubles the memory bandwidth. The Dutch National Flag algorithm touches each cell once, which can matter on very large arrays or on memory-constrained hardware.

If the array can contain values outside the {0, 1, 2} alphabet, the else branch is wrong: any unexpected value would be routed into the twos region. In production code, add an explicit check that throws IllegalArgumentException for any element that is not one of the three expected values. This keeps the invariant honest.

Interview Follow-up Questions

Once you solve the base problem, a strong interviewer will probe your understanding with variations. Here are the ones that come up most often, ordered from easiest to hardest.

• Can you solve it with a two-pass counting algorithm instead? – count the frequency of each value in one pass, then overwrite the array using those counts; still O(n) time but with two passes over the data.
• What if the alphabet is {0, 1, 2, 3} or larger? – the three-pointer trick does not generalize cleanly; use counting sort for a bounded alphabet or fall back to a general O(n log n) sort.
• Can you preserve the relative order of equal elements? – the in-place three-pointer version is not stable; a stable solution needs an auxiliary array and O(n) extra space.
• How would you solve it if the array is a read-only stream? – you cannot swap in place; buffer each class of value into its own queue as the stream arrives, then emit the queues in order when the stream ends.
• What if the array has billions of elements and does not fit in memory? – partition each chunk on disk, write zeros, ones, and twos to three output files, then concatenate the files. The chunk step is embarrassingly parallel.

Conclusion

Separating zeros, ones, and twos is a compact exercise that rewards a clear three-pointer mental model and a crisp statement of the loop invariant. Once you can describe the four regions out loud, the implementation almost writes itself, and the common mistakes become easy to spot in your own code.

Try adapting the method to partition by any three-valued key, or extend it into a stable counting-based variant; both are frequent interview sequels. You can learn more about array techniques here: Arrays.