Problem Statement
Sort Colors
You have a list of items, each one colored red, white, or blue. In the list these colors are written as numbers: red is 0, white is 1, and blue is 2. Your job is to rearrange the list so all the reds come first, then all the whites, then all the blues. You must do it in-place, which means you rearrange the same list directly instead of building a new one. The trick we use is called the Dutch National Flag algorithm (a flag has three stripes of color, just like our three colors). The idea is to use three pointers, which are just markers that remember a position in the list. We call them low, mid, and high. As we go, the list splits into four zones: everything before low is settled 0s, the part from low up to mid is settled 1s, the part from mid to high is still unsorted, and everything after high is settled 2s.
Signals to notice
Brute force first
Counting sort (count 0s, 1s, 2s, overwrite) — but two passes. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Dutch National Flag: three pointers — low (next 0 position), mid (current), high (next 2 position). Swap 0s to front, 2s to back, 1s stay in middle. Single pass. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on nums=[2,0,2,1,1,0]
init: low=0, mid=0, high=5, arr=[2,0,2,1,1,0] mid=0: nums[mid]=2 -> swap(mid,high); high=4; arr=[0,0,2,1,1,2] mid=0: nums[mid]=0 -> swap(low,mid); low=1, mid=1 (arr unchanged) mid=1: nums[mid]=0 -> swap(low,mid); low=2, mid=2 (arr unchanged) mid=2: nums[mid]=2 -> swap(mid,high); high=3; arr=[0,0,1,1,2,2] mid=2: nums[mid]=1 -> mid=3 mid=3: nums[mid]=1 -> mid=4; now mid>high, loop ends return [0,0,1,1,2,2]
What must stay true
Everything before low is 0, everything after high is 2, everything between low and mid is 1. Mid scans through unsorted elements. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
low, mid = 0, 0; high = n - 1
while mid <= high:
if nums[mid] == 0: swap(low, mid); low++; mid++
elif nums[mid] == 1: mid++
else: swap(mid, high); high-- # don't advance midPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not incrementing mid when swapping with high — the element swapped from high hasn't been examined yet, so don't advance mid. When swapping with low, both mid and low advance because the swapped element is known to be 1. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.