Dutch national flag algorithm: three pointers partition 0s, 1s, and 2s in one pass without counting or using library sort.

Sort Colors

Problem

A renderer pipeline processes pixels tagged as dark (0), neutral (1), or bright (2) and must group them by tag before applying layer effects. Sort an array containing only 0s, 1s, and 2s in-place in a single pass without using any library sort function.

Example 1:

Input: [2,1,2,0,0,1]
Output: [0,0,1,1,2,2]

Example 2:

Input: [1,2,0]
Output: [0,1,2]

Example 3:

Input: [0]
Output: [0]
Explanation: A single element is already sorted.

Constraints:

1 <= nums.length <= 300
nums[i] is 0, 1, or 2

Try it

def sort_colors(nums: list[int]) -> None:
    pass

Tests

a = [2,1,2,0,0,1]; sort_colors(a); assert a == [0,0,1,1,2,2], "general case"
b = [1,2,0]; sort_colors(b); assert b == [0,1,2], "one of each"
c = [0]; sort_colors(c); assert c == [0], "single element"
d = [0,0,0]; sort_colors(d); assert d == [0,0,0], "all zeros"
e = [2,2,0,1,0,1]; sort_colors(e); assert e == [0,0,1,1,2,2], "mixed"

Hints (3)

Solution Breakdown

Approach: Dutch national flag - a single-pass three-way partition.

Three pointers carve the array into four regions: [0..low-1] are settled 0s, [low..mid-1] are settled 1s, [mid..high] is still unexamined, and [high+1..n-1] are settled 2s. Start with low = mid = 0 and high = len(nums) - 1 so the entire array is unexamined, then advance mid until it passes high. At each step the value at mid decides the move. If it is a 0, swap it down to nums[low] and advance both low and mid - the element swapped up came from the 1s region (or is mid itself), so it is already correct and mid can move on. If it is a 2, swap it up to nums[high] and decrement high only, leaving mid in place because the element that just arrived from the back has not been examined yet. If it is a 1, it already belongs in the middle, so just advance mid.

Trace [2,1,2,0,0,1]: mid=0 sees a 2, swap with index 5, high drops to 4, array [1,1,2,0,0,2]; mid=0 now sees a 1, mid advances to 1; mid=1 sees a 1, mid advances to 2; mid=2 sees a 2, swap with index 4, high drops to 3, array [1,1,0,0,2,2]; mid=2 sees a 0, swap with low, low=1, mid=3; mid=3 sees a 0, swap with low, low=2, mid=4 > high=3, loop ends, leaving [0,0,1,1,2,2] (the swap at the last step restored the 0 to position 1).

Edge cases: All-same inputs like [0,0,0] (mid walks straight through) or [2,2,2] (high marches down to meet mid) and a single element are all handled by the mid <= high bound with no special-casing.

Complexity: O(n) time, O(1) space - one pass, each element swapped at most once into place, only three integer pointers.

Sort Colors

Problem

Solution Breakdown

Discussion