Dutch National Flag Algorithm for Three-Way Partitioning

1. The "Sort Colors" Problem

Imagine you're given an array of integers, but this array only contains 0s, 1s, and 2s. The task is to sort this array in-place (meaning you cannot create a new array) so that all the 0s come first, followed by all the 1s, and finally all the 2s.

For example, given the input [2, 0, 2, 1, 1, 0], the output should be [0, 0, 1, 1, 2, 2].

The name "Dutch National Flag" comes from the analogy of sorting balls of three colors—red, white, and blue—into the order of the Dutch flag.

2. Thinking Through the Solutions

Before jumping to the optimal solution, let's consider a couple of straightforward approaches, as this is a great way to think during an interview.

1. Use a standard sorting algorithm: The simplest way is to call Arrays.sort() on the array. This would work, but it doesn't take advantage of the fact that we only have three distinct values. An interviewer would ask for a more tailored solution, as a general-purpose sort is typically O(n log n).

2. Count and Overwrite (Two-Pass Solution): A better approach is to iterate through the array once to count the occurrences of 0s, 1s, and 2s. Then, in a second pass, you overwrite the original array with the correct number of 0s, then 1s, then 2s. This works in O(n) time and O(1) space. It's a good solution, but can we do it in a single pass?

The "take U forward" channel provides a great overview of these approaches, setting the stage for the optimal one.

3. The Optimal Approach: Dutch National Flag Algorithm

The most efficient solution, the Dutch National Flag algorithm, solves this problem in a single pass using a clever three-pointer approach. The core idea is to partition the array into four conceptual sections as we iterate through it:

1. arr[0 ... low-1]: Section of 0s. All elements here are confirmed to be 0.
2. arr[low ... mid-1]: Section of 1s. All elements here are confirmed to be 1.
3. arr[mid ... high]: Unknown section. These are the elements we haven't processed yet.
4. arr[high+1 ... n-1]: Section of 2s. All elements here are confirmed to be 2.

We use three pointers to manage these sections:

• low: Marks the boundary after the last known 0.
• mid: The current element being considered. It scans the array.
• high: Marks the boundary before the first known 2.

Our goal is to shrink the unknown section (mid to high) until it disappears. The algorithm proceeds with the mid pointer, and we have three cases depending on the value of arr[mid]:

• Case 1: arr[mid] == 0

  • A 0 is in the wrong place. We need to move it to the low section.
  • Action: Swap arr[low] and arr[mid].
  • Pointer Update: Increment both low and mid. We increment low because we've added a 0 to its section. We increment mid because the element we just swapped into arr[low] was a 1 (from the 1s section) or we swapped with ourselves, so we can move on.

• Case 2: arr[mid] == 1

  • A 1 is in the right place (it's between the 0s and the unknown zone).
  • Action: Do nothing.
  • Pointer Update: Increment mid to process the next element.

• Case 3: arr[mid] == 2

  • A 2 is in the wrong place. We need to move it to the high section.
  • Action: Swap arr[high] and arr[mid].
  • Pointer Update: Decrement high. Crucially, we do not increment mid. The element we just swapped from arr[high] is unknown. It could be a 0, 1, or 2, and it needs to be processed in the next iteration.

The loop continues as long as mid <= high.

The following video provides an excellent visual demonstration of this process.

4. Java Implementation

Now, let's look at a clean Java implementation of the algorithm. This code directly translates the logic we just discussed.

Here's the code from the article for easy reference:

import java.util.Arrays;

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

        // Iterate until mid pointer crosses the high pointer
        while (mid <= high) {
            switch (nums[mid]) {
                // Case for 0
                case 0: {
                    temp = nums[low];
                    nums[low] = nums[mid];
                    nums[mid] = temp;
                    low++;
                    mid++;
                    break;
                }
                // Case for 1
                case 1: {
                    mid++;
                    break;
                }
                // Case for 2
                case 2: {
                    temp = nums[mid];
                    nums[mid] = nums[high];
                    nums[high] = temp;
                    high--;
                    // Do not increment mid here!
                    break;
                }
            }
        }
    }
}

// Driver code to test
class Main {
    public static void main(String[] args) {
        Solution obj = new Solution();
        int[] nums = {2, 0, 2, 1, 1, 0};
        System.out.println("Original array: " + Arrays.toString(nums));
        
        obj.sortColors(nums);
        
        System.out.println("Sorted array:   " + Arrays.toString(nums));
        // Expected output: [0, 0, 1, 1, 2, 2]
    }
}

Note: I've used a switch statement here as shown in some implementations, which is equivalent to the if-else if-else logic.

5. Complexity Analysis

Let's analyze the efficiency of this algorithm, which is crucial for interviews.

• Time Complexity: O(n)
  The algorithm processes the array in a single pass. Each element is visited by the mid pointer at most once. The swaps are constant-time operations. Therefore, the time complexity is linear with respect to the number of elements in the array.

• Space Complexity: O(1)
  The sorting is done in-place. We only use a few extra variables (low, mid, high, temp) to hold pointers and for swapping. The amount of extra space does not grow with the size of the input array, making it a constant space solution.

Conclusion

You've now learned the Dutch National Flag algorithm, a powerful and efficient method for three-way partitioning. It's a prime example of how a deep understanding of the problem's constraints (only three unique values) can lead to a more optimal solution than a general-purpose algorithm.

Key Takeaways:

• Problem: Sort an array of 0s, 1s, and 2s in-place and in a single pass.
• Algorithm: The Dutch National Flag algorithm uses three pointers (low, mid, high) to partition the array into sections of 0s, 1s, and 2s.
• Core Logic: Iterate with the mid pointer and swap elements based on whether arr[mid] is 0, 1, or 2, shrinking the "unknown" part of the array.
• Efficiency: The algorithm is highly efficient with O(n) time complexity and O(1) space complexity.

Preview of the next lesson:
We'll continue our tour of clever array algorithms by looking at the Boyer-Moore Voting Algorithm. This is another single-pass, O(1) space algorithm used to find the majority element in an array (an element that appears more than n/2 times). It's another interview classic that showcases non-intuitive but highly effective logic.