Sort Colors
How to group an array of only three distinct values — 0, 1, and 2 — in a single pass, with no extra array and no counting step first.
The job
You have an array where every value is 0, 1, or 2. Rearrange it so every 0 comes first, then every 1, then every 2 — in one pass, in place.
The obvious way
Count how many 0s, 1s, and 2s there are, then overwrite the array with that many of each in order — two passes, and it needed to know the full counts first.Two full passes over the array, plus a small counting array.
The idea
Keep three positions: `low` and `high` mark the boundaries of the 0-group and 2-group, growing inward as values are confirmed. `mid` scans between them — a 0 gets swapped down to `low`, a 2 gets swapped up to `high`, and a 1 is already exactly where it belongs, so `mid` just steps past it.
Think of it like this. Sorting a laundry basket of red, white, and blue socks by tossing each one straight into its own pile as you touch it — reds pile up on the left, blues on the right, whites stay in the middle — instead of sorting the whole pile by counting colors first.
Three regions, one scan
6 values, each 0, 1, or 2. Group them in one pass: all the 0s first, then the 1s, then the 2s.
def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1This run
Every value is grouped: 0s first, then 1s, then 2s — sorted in one left-to-right pass over 6 positions, no extra array.
The names you just watched
low, mid, high
`low` and `high` mark confirmed boundaries and only ever move inward. `mid` is the only pointer that actually reads values, and it always sits between the other two.
Why mid doesn't always advance
Swapping with `low` brings a value already known to be 0 or 1 into `mid`'s slot, so it is safe to step past. Swapping with `high` brings an UNKNOWN value in — it must be checked again.
One pass, not two
Because every value is classified and placed the moment `mid` reaches it, there is no separate counting pass and no second write-through of the array.
How to spot this shape
The tell: You need to partition an array into three known, ordered groups in place, and a brute-force answer would count each group first and rebuild the array from those counts.
Reach for it when
- The values fall into a small, fixed number of categories (here, exactly three).
- The target order of the categories is known in advance.
- The task explicitly forbids extra space or a full sort.
- A two-region version of the same idea (see Move Zeroes) is the natural warm-up.
Not this when
- The categories are not known in advance, or there are many of them — that wants counting sort or a hash map instead.
- A full comparison sort is acceptable — this technique only pays off because the domain is tiny.
- The elements are not randomly accessible (e.g. a linked list) — the swap-based walk does not translate directly.
Practice
6 problemsThe lesson, exactly. Three regions, one scanning pointer, at most one pass.
The two-region version of this exact idea — one write pointer instead of two.
Quickselect uses the same three-way partition around a pivot — just with an arbitrary pivot value instead of a fixed 0/1/2.
Find the median, then three-way partition around it with a virtual index mapping — the same low/mid/high shape in disguise.
A two-region partition (even vs. odd) — the low/high half of this lesson without the middle group.
Two SEPARATE scanning pointers (one over even slots, one over odd slots) instead of one shared mid — a variation worth comparing against this lesson’s single-scanner shape.