Dutch National Flag (3-Way Partition)

You are given an array containing only 0s, 1s, and 2s, and you need to sort it in-place. This is LeetCode 75, Sort Colors, and it is one of the most elegant problems in the two-pointer family. The constraint that makes it interesting: you should do it in a single pass.

If you reach for a general-purpose sorting algorithm, you will get $O(n \log n)$ time. That works, but it ignores the fact that there are only three distinct values. Using $O(n \log n)$ sorting on three values is like hiring a moving company to rearrange three books on a shelf. You could also count the occurrences of each value and then overwrite the array in a second pass. That is $O(n)$ time, but it requires two passes and does not generalize well to problems where you are partitioning objects with associated data (you cannot just overwrite them). The real question is: can you do it in one pass with $O(1)$ space, moving each element to its final position by swapping?

The answer is Dijkstra's Dutch National Flag algorithm.

Three pointers, one invariant

The algorithm uses three pointers: lo, mid, and hi. At every step, the array satisfies this invariant:

• Everything in [0, lo) is 0 (the "red" zone).
• Everything in [lo, mid) is 1 (the "white" zone).
• Everything in (hi, end] is 2 (the "blue" zone).
• Everything in [mid, hi] is unexamined.

Initially lo = 0, mid = 0, and hi = n - 1, so the entire array is unexamined. The algorithm processes elements by looking at nums[mid] and making one of three decisions.

If nums[mid] == 0, it belongs in the red zone. Swap nums[mid] with nums[lo], then advance both lo and mid. The value that was at lo must have been a 1 (it was in the white zone between lo and mid), so after the swap mid is pointing at a known value and can safely advance.

If nums[mid] == 1, it is already in the right place. Just advance mid.

If nums[mid] == 2, it belongs in the blue zone. Swap nums[mid] with nums[hi], then decrement hi. But, and this is the critical detail, do not advance mid. The value that was at hi is unexamined. It could be a 0, a 1, or a 2. You need to inspect it before moving on.

The loop continues while mid <= hi. When they cross, every element has been examined and placed into its correct zone.

Walking through an example

Start with the array [2, 0, 2, 1, 1, 0] and initialize lo = 0, mid = 0, hi = 5.

Step 1: nums[mid] = nums[0] = 2. This is a 2, so swap nums[0] with nums[5] and decrement hi. Array becomes [0, 0, 2, 1, 1, 2]. Now lo = 0, mid = 0, hi = 4. Notice we did not advance mid: the 0 we just swapped in has not been examined yet.

Step 2: nums[mid] = nums[0] = 0. This is a 0, so swap nums[0] with nums[0] (a no-op since lo == mid) and advance both. Array stays [0, 0, 2, 1, 1, 2]. Now lo = 1, mid = 1, hi = 4.

Step 3: nums[mid] = nums[1] = 0. Another 0. Swap nums[1] with nums[1] (again lo == mid), advance both. Array stays [0, 0, 2, 1, 1, 2]. Now lo = 2, mid = 2, hi = 4.

Step 4: nums[mid] = nums[2] = 2. Swap nums[2] with nums[4] and decrement hi. Array becomes [0, 0, 1, 1, 2, 2]. Now lo = 2, mid = 2, hi = 3. Again, we do not advance mid.

Step 5: nums[mid] = nums[2] = 1. Just advance mid. Array stays [0, 0, 1, 1, 2, 2]. Now lo = 2, mid = 3, hi = 3.

Step 6: nums[mid] = nums[3] = 1. Advance mid. Now mid = 4, which is greater than hi = 3, so the loop ends.

Final array: [0, 0, 1, 1, 2, 2]. Sorted in one pass.

Why you must not advance mid when swapping with hi

This is the single most important detail in the algorithm, and the one most people get wrong on their first attempt. When you swap nums[mid] with nums[lo], you advance mid because you know what came from position lo: it was in the range [lo, mid), the white zone, so it must be a 1. You have already processed it. Safe to skip.

But when you swap nums[mid] with nums[hi], you are pulling a value from the unprocessed region. You have no idea whether it is a 0, 1, or 2. If you blindly advance mid, you might skip over a 0 that should have been swapped to the left. So you must leave mid in place and examine the newly swapped value on the next iteration.

If you forget this and advance mid in both swap cases, the algorithm will appear to work on some inputs but silently produce wrong results on others. This asymmetry between the two swap operations is the heart of the algorithm.

Code for Sort Colors

def sortColors(nums):
    lo, mid, hi = 0, 0, len(nums) - 1
    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1

There are no edge cases to worry about. If the array is empty or has one element, the loop simply never executes or executes once harmlessly. The algorithm handles all-zeros, all-twos, and already-sorted arrays without any special logic.

3-way quicksort partition

The Dutch National Flag algorithm is not just a curiosity for sorting three colors. It is the basis of 3-way partitioning in quicksort, which handles duplicate elements efficiently.

In standard quicksort, you pick a pivot and partition the array into elements less than the pivot and elements greater than or equal to the pivot. If the array has many duplicates, say all elements are the same value, standard quicksort degrades to $O(n^2)$ because every partition puts all elements on one side.

3-way partition quicksort fixes this by partitioning into three groups: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. The mechanism is exactly the Dutch National Flag algorithm, with "less than pivot" playing the role of 0, "equal to pivot" playing the role of 1, and "greater than pivot" playing the role of 2. Elements equal to the pivot land in the middle group and are already in their final sorted positions, so they never need to be recursively sorted.

def three_way_partition(arr, lo_bound, hi_bound, pivot):
    lo, mid, hi = lo_bound, lo_bound, hi_bound
    while mid <= hi:
        if arr[mid] < pivot:
            arr[lo], arr[mid] = arr[mid], arr[lo]
            lo += 1
            mid += 1
        elif arr[mid] == pivot:
            mid += 1
        else:
            arr[mid], arr[hi] = arr[hi], arr[mid]
            hi -= 1
    return lo, hi

After this function returns, arr[lo_bound..lo-1] contains elements less than the pivot, arr[lo..hi] contains elements equal to the pivot, and arr[hi+1..hi_bound] contains elements greater than the pivot. The recursive calls only need to process the less-than and greater-than ranges, completely skipping all duplicates of the pivot.

For arrays with many repeated values, this turns $O(n^2)$ worst-case quicksort into $O(n \log n)$ expected time. In the extreme case where all elements are equal, the very first partition puts everything in the middle group and recursion bottoms out immediately, for $O(n)$ total.

Move Zeroes: the simpler two-way version

A simpler variant appears in LeetCode 283, Move Zeroes, which asks you to move all 0s in an array to the end while maintaining the relative order of the non-zero elements. This is essentially a 2-way partition: you only have two categories (zero and non-zero) instead of three.

You can solve it with just two pointers: a write pointer lo that tracks where the next non-zero should go, and a read pointer i that scans through the array. Whenever nums[i] is non-zero, swap it with nums[lo] and advance lo. This is a simplified Dutch National Flag with only two of the three branches.

def moveZeroes(nums):
    lo = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[lo], nums[i] = nums[i], nums[lo]
            lo += 1

The Dutch National Flag algorithm generalizes this idea from two categories to three, which is exactly the step that requires the third pointer and the subtle "do not advance mid" rule.

Complexity analysis

The Dutch National Flag algorithm runs in $O(n)$ time. Each iteration of the loop either advances mid forward or moves hi backward (or both in the case where lo and mid advance together). Since mid starts at 0 and hi starts at n - 1, and neither pointer ever reverses direction, the total number of iterations is at most n. Every operation inside the loop, a comparison, a swap, and pointer updates, is $O(1)$.

Space complexity is $O(1)$. The algorithm sorts in-place using only three integer variables regardless of the input size. All rearrangement happens through swaps, so no auxiliary storage is needed.

Recognizing this pattern

You're probably looking at Dutch National Flag when:

• You need to partition an array into three buckets in-place in a single pass with $O(1)$ extra space.
• The values come from a small fixed set (0/1/2, low/mid/high, less-than/equal-to/greater-than-pivot).
• The problem says "sort colors" or asks for a 3-way partition around a pivot.
• A counting-sort-and-overwrite is disallowed because elements carry attached data you cannot reconstruct.

Common templates:

• Three-value sort: lo, mid, hi pointers; mid scans, swap with lo for low values and with hi for high values. Example: Sort Colors.
• Quicksort 3-way partition: partition around a pivot into less / equal / greater; useful for arrays with many duplicates. Example: Kth Largest Element in an Array.
• Move-zeroes / partition-by-predicate: degenerate two-bucket version that splits into "zero" and "non-zero" while preserving order on one side. Example: Move Zeroes.
• Wiggle-sort partitioning: partition around the median, then interleave. Example: Wiggle Sort II.