LeetCode #75 Medium

Sort Colors

Sort an array of 0s, 1s, and 2s in place in a single pass (the Dutch National Flag problem).

arraytwo-pointersdutch-flag

02

Intuition

💡

Maintain three regions: settled 0s on the left, settled 2s on the right, and unexamined values in the middle. A single mid pointer scans; 0s are swapped down to the low boundary, 2s swapped up to the high boundary, 1s left alone.

03

Approach

1

Counting works, but it's two passes

The simplest correct solution counts how many 0s, 1s, and 2s there are, then overwrites the array in order — two passes. The classic challenge is to do it in one pass and in place, which forces us to place each value correctly the first time we see it. With only three distinct values, we can partition the array as we scan.

2

Three regions, three pointers

Maintain three boundaries: low (end of the settled 0s), high (start of the settled 2s), and mid (the scanner). The invariant is: everything before low is 0, everything from low to mid is 1, everything after high is 2, and mid..high is the unexamined middle. Each value tells mid what to do: a 0 swaps down to the low boundary, a 2 swaps up to the high boundary, a 1 is already in the right region.

3

The subtle part: don't advance mid on a 2

When nums[mid] == 0 you swap with low and advance both (the swapped-in value came from the 1-region, so it's a known 1). When it's a 1, just advance mid. But when it's a 2, you swap with high and shrink high without advancing mid — because the value swapped in from the right is unexamined and must be re-checked. Loop while mid <= high; when they cross, every value is placed. One pass, O(n) time, O(1) space.

04

Solution & live demo

python

▶1class Solution:
▶2    def sortColors(self, nums):
▶3        low, mid, high = 0, 0, len(nums) - 1
▶4        while mid <= high:
▶5            if nums[mid] == 0:
▶6                nums[low], nums[mid] = nums[mid], nums[low]
▶7                low += 1
▶8                mid += 1
▶9            elif nums[mid] == 1:
▶10                mid += 1
▶11            else:
▶12                nums[mid], nums[high] = nums[high], nums[mid]
▶13                high -= 1

05

Edge cases

Already sorted, e.g. [0,1,2]

0 swaps with itself, 1 is skipped, 2 swaps with itself — order is preserved.

All identical values

All-0 advances both low and mid; all-2 shrinks high; all-1 just advances mid. Each terminates cleanly.

A 2 swapped to mid that is also a 2

Because mid does not advance on a 2-swap, the freshly swapped value is re-examined, never skipped.

06

Complexity

Time

O(n)

Space

O(1)

One pass, in place, three pointers.