Two Pointers · LC #75

Sort Colors

Dutch National Flag algorithm: three pointers partition 0s, 1s, and 2s in a single pass. The "do not advance mid when swapping with hi" subtlety is the key interview insight.

mediumLC #75AMZ★★GOO★META★★MSFT★★AAPL★★

Mark as done

Confidence

Ask GPT Practice on LeetCodePractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Given array `nums` with values 0, 1, 2 (representing red, white, blue), sort them in-place so all 0s come first, then 1s, then 2s. Must be one pass with O(1) extra space.

Sample I/O

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

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

Time: O(n) · Space: O(1)

Intuition

How to Think About It

Intuition

Three distinct values map cleanly to three regions: [0..lo) = all 0s, [lo..mid) = all 1s, [mid..hi] = unknown, (hi..n-1] = all 2s. The mid pointer processes the unknown region. When it encounters 0, swap with lo (both pointers advance). When 1, just advance mid. When 2, swap with hi (hi retreats but mid stays - the swapped element is unknown).

Core Concept

lo=0, mid=0, hi=n-1. While mid ≤ hi: if nums[mid]==0 → swap(lo,mid), lo++, mid++; elif nums[mid]==1 → mid++; else → swap(mid,hi), hi-- (no mid++).

When to use

Any three-way partition (less/equal/greater than pivot - used in 3-way quicksort). Partitioning an array into exactly 3 categories.

When NOT to use

More than 3 categories - use counting sort. When stability is required (DNF is not stable).

Key Insights

What to Know Cold

When swapping nums[mid] with nums[hi] (a 2), do NOT increment mid - the incoming element from hi is unknown and needs to be processed.
When swapping nums[mid] with nums[lo] (a 0), DO increment both lo and mid - nums[lo] was already processed (it is a 1 that was placed there earlier, or we are at the start).
The invariant at all times: [0..lo)=0s, [lo..mid)=1s, (hi..n-1]=2s.
This is Dijkstra's Dutch National Flag algorithm, generalises to 3-way quicksort partition.
A two-pass count-then-fill approach is simpler but violates the "one pass" requirement.

1 example

Worked Examples

Dutch National Flag - Three-Pointer Partition

[2,0,2,1,1,0]. Sort into 0s, 1s, 2s in one pass.

lo=mid=0, hi=5. nums[mid]=2 → swap with hi=5 (nums[5]=0), hi=4. Now nums[mid]=0 → swap with lo=0, lo=1, mid=1. Continue until mid>hi.

def sortColors(nums: list[int]) -> None:
    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  # do NOT increment mid

Dijkstra's DNF is the canonical three-way partition - underpins 3-way quicksort and appears in AAPL and MSFT system design discussions about in-place partitioning.