Dutch Flag Algorithm: Sort 0s 1s 2s in O(n) Time

Understanding the Sorting Problem

Arrays containing only 0s, 1s, and 2s appear frequently in coding interviews, with LeetCode Problem 75 ("Sort Colors") being a prime example. After analyzing this video, I recognize three critical approaches developers should understand. The naive sorting solution uses library functions (O(n log n)), while the counting method improves to O(n) with two passes. However, the Dutch National Flag algorithm provides the optimal single-pass solution—a technique extending to similar partitioning problems.

Brute Force Approach Limitations

Simply calling sort(nums.begin(), nums.end()) provides an O(n log n) solution but violates core problem constraints prohibiting library functions. This approach fails interview settings where manual implementation demonstrates algorithmic understanding. While functional for small datasets, its inefficiency becomes apparent at scale.

Counting Method Implementation

Initialize counters: count0, count1, count2. Traverse the array once to tally elements. Then:

1. Fill first count0 indices with 0
2. Next count1 indices with 1
3. Remaining positions with 2

# Python implementation
def sortColors(nums):
    count0 = count1 = count2 = 0
    for num in nums:
        if num == 0: count0 += 1
        elif num == 1: count1 += 1
        else: count2 += 1
    nums[:count0] = [0]*count0
    nums[count0:count0+count1] = [1]*count1
    nums[count0+count1:] = [2]*count2

Time Complexity: O(2n) ≈ O(n) | Space Complexity: O(1)
This two-pass approach is acceptable but suboptimal for massive datasets where single-pass solutions matter.

Dutch National Flag Algorithm

Developed by Edsger Dijkstra, this algorithm partitions arrays into three sections using three pointers:

• low tracks start of 1s (end of 0s)
• mid processes current element
• high tracks start of 2s

Algorithm Steps

1. Initialize low, mid = 0 and high = len(nums)-1
2. While mid <= high:
   • Case 0: Swap nums[low] and nums[mid]. Increment both low and mid
   • Case 1: Increment mid (element already in correct partition)
   • Case 2: Swap nums[mid] and nums[high]. Decrement high

def dutchFlagSort(nums):
    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

Why this works: Each swap operation places 0s at the front and 2s at the back, while 1s naturally converge in the middle. The single pass ensures O(n) time with O(1) space.

Real-World Applications

Beyond sorting colors, this algorithm partitions datasets for:

1. Three-way quicksort optimization
2. RGB image processing pipelines
3. E-commerce inventory filtering (e.g., low/medium/high stock)
   Not covered in the video: This technique extends to any ternary categorization problem where in-place partitioning is required.

Implementation Checklist

1. Initialize low, mid at 0, high at last index
2. Loop while mid <= high
3. For current element nums[mid]:
   • 0 → Swap with nums[low]; increment low and mid
   • 1 → Increment mid
   • 2 → Swap with nums[high]; decrement high
4. Verify edge cases: empty array, all elements same

Complexity Analysis

Approach	Time Complexity	Space Complexity	Passes
Library Sort	O(n log n)	O(1)	N/A
Counting Method	O(n)	O(1)	2
Dutch Flag	O(n)	O(1)	1

Key Insight: The Dutch Flag algorithm minimizes operations by processing each element exactly once, making it ideal for high-frequency trading systems or embedded devices with memory constraints.

Recommended Resources

• Book: Algorithms by Sedgewick & Wayne (partitioning techniques)
• Practice Platform: LeetCode Problem 75 ("Sort Colors")
• Visualization Tool: VisuAlgo.net/sorting (select "3-Way Partition")

"Which partition case (0, 1, or 2) gave you the most trouble during implementation? Share your debugging experience below!"

Final Thought: Mastering this single-pass algorithm demonstrates advanced understanding of in-place operations—a critical skill for optimization-heavy roles at FAANG companies.