Sort an Array of 0's, 1's, and 2's (Dutch National Flag Algorithm)

1. Why Do We Need This? (Problem Statement & Status Quo)

When given an array containing only three unique integers (0, 1, and 2), the objective is to sort the array in-place such that all 0s appear first, followed by all 1s, and all 2s conclude the array.

While sorting might initially sound trivial, relying on generic sorting algorithms or inefficient auxiliary structures fails to impress technical interviewers. Understanding the progressive optimization—from Brute Force to Better to the Optimal Dutch National Flag Algorithm—is essential for mastering linear-time in-place sorting patterns.

2. Approach 1: The Brute Force Solution

The most immediate approach that comes to mind is applying a standard comparison-based sorting algorithm.

Mechanics & Complexity

• Strategy: Pass the array directly into a general-purpose sorting routine (such as Merge Sort or Quick Sort).
• Time Complexity: $\mathcal{O}(N \log N)$ because of the comparison-based sorting overhead.
• Space Complexity: $\mathcal{O}(N)$ or $\mathcal{O}(\log N)$ depending on the auxiliary sorting space requirements (e.g., temporary arrays used during Merge Sort).

Unsorted Array [2, 0, 2, 1, 1, 0]
   |
   | applies Merge Sort (O(N log N))
   v
Sorted Array [0, 0, 1, 1, 2, 2]

Note: Interviewers will reject this approach because we have a specialized constraint: the array only contains 0, 1, and 2. A generic $\mathcal{O}(N \log N)$ sort ignores this domain-specific knowledge.

3. Approach 2: The Better Solution (Counting Approach)

Since we know the elements are strictly restricted to 0, 1, and 2, we can avoid comparison sorting entirely by counting the frequency of each number.

Step-by-Step Execution

1. First Pass (Counting): Iterate through the array once and maintain three frequency counters: count0, count1, and count2.
2. Second Pass (Overwriting): Run subsequent loops to manually overwrite the original array:
   • Fill the first count0 positions with 0.
   • Fill the next count1 positions with 1.
   • Fill the remaining count2 positions with 2.

Code Implementation (Conceptual)

void sortZeroOneTwo(vector<int>& arr) {
    int count0 = 0, count1 = 0, count2 = 0;
    
    // Pass 1: Count frequencies
    for (int num : arr) {
        if (num == 0) count0++;
        else if (num == 1) count1++;
        else count2++;
    }
    
    // Pass 2: Overwrite array based on counts
    for (int i = 0; i < count0; i++) arr[i] = 0;
    for (int i = count0; i < count0 + count1; i++) arr[i] = 1;
    for (int i = count0 + count1; i < arr.size(); i++) arr[i] = 2;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N) + \mathcal{O}(N) = \mathcal{O}(2N)$, which simplifies to $\mathcal{O}(N)$ because it requires two full passes over the array.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space, as modifications happen directly in-place without extra data structures.

Note: While $\mathcal{O}(N)$ time and $\mathcal{O}(1)$ space is efficient, the interviewer will challenge you: "You are taking two passes ($\mathcal{O}(2N)$). Can you solve this in a single pass ($\mathcal{O}(N)$ with exactly one iteration)?"

4. Approach 3: The Optimal Solution — Dutch National Flag Algorithm

To achieve a single-pass, in-place sort, we use the Dutch National Flag Algorithm (named after Edsger Dijkstra's programming exercise).

Real-Life Analogy: Sorting Colored Balls in a Line

Imagine you have a row of mixed balls colored red, white, and blue (representing 0, 1, and 2). You want to sort them such that all reds are on the left, whites are in the middle, and blues are on the right. Instead of picking up and moving everything blindly, you walk down the line using three strategic fingers/pointers to inspect elements one by one, swapping them instantly into their designated zones.

5. The Three-Pointer Architecture & Invariants

The algorithm relies on three distinct pointers (low, mid, and high) that partition the array into four conceptual sections:

Diagrammatic Breakdown of Pointers

Array Indices:  [ 0 ... low-1 ] | [ low ... mid-1 ] | [ mid ... high ] | [ high+1 ... n-1 ]
Contents:       [   Zeros     ] | [    Ones     ] | [  Unsorted  ] | [    Twos      ]
Pointers:                         ^ (low)             ^ (mid)          ^ (high)

Core Invariant Rules

1. 0 to low - 1: Always contains 0.
2. low to mid - 1: Always contains 1.
3. mid to high: Unsorted elements to be evaluated.
4. high + 1 to n - 1: Always contains 2.

6. Step-by-Step Execution Logic (Examining arr[mid])

The algorithm inspects the element at the mid pointer (arr[mid]) and branches into three distinct conditions:

Case 1: arr[mid] == 0

• Action: Swap arr[low] and arr[mid].
• Pointer Movement: Increment both low and mid (low++, mid++).
• Rationale: The zero is moved into the left boundary (expanding the 0 zone), and mid moves forward because the swapped element from low is guaranteed to be a processed 1 or 0.

Case 2: arr[mid] == 1

• Action: Do nothing to the elements.
• Pointer Movement: Increment only mid (mid++).
• Rationale: The element is already in the correct middle zone (1), so we expand the 1 boundary by moving mid ahead.

Case 3: arr[mid] == 2

• Action: Swap arr[mid] and arr[high].
• Pointer Movement: Decrement only high (high--).
• Rationale: Send the 2 to the extreme right zone. Notice that mid is not incremented here because the element swapped from high is unknown and must be evaluated in the next iteration.

7. Complete Code Implementation (C++, Java, Python)

C++ Implementation

#include <vector>
#include <algorithm>

using namespace std;

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } 
        else if (nums[mid] == 1) {
            mid++;
        } 
        else { // nums[mid] == 2
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

Java Implementation

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        
        while (mid <= high) {
            if (nums[mid] == 0) {
                int temp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = temp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                int temp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = temp;
                high--;
            }
        }
    }
}

Python Implementation

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low, mid, high = 0, 0, len(nums) - 1
        
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else: # nums[mid] == 2
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

8. Comparative Strategy Synthesis

9. Summary and Key Takeaways

• Problem Constraints Drive Optimization: Recognizing that inputs are limited to three discrete integers (0, 1, 2) eliminates the need for comparison-based $\mathcal{O}(N \log N)$ sorting.
• Single-Pass Efficiency: The Dutch National Flag algorithm accomplishes sorting in a single pass ($\mathcal{O}(N)$ time) with constant auxiliary space ($\mathcal{O}(1)$ space).
• Three-Pointer Partitioning: The array is dynamically partitioned into four segments using low, mid, and high pointers.
• Pointer Invariants Matter:
  • 0 to low - 1 holds 0s.
  • low to mid - 1 holds 1s.
  • high + 1 to n - 1 holds 2s.
• Conditional Mid Behavior:
  • If 0: Swap with low, increment both low and mid.
  • If 1: Increment mid directly.
  • If 2: Swap with high, decrement high (without moving mid so the swapped element can be evaluated).
• Loop Termination: The algorithm terminates cleanly when mid crosses high (mid > high), guaranteeing the entire array is sorted.