STEP 3 · ARRAYS · THREE-WAY PARTITION · MEDIUM

Sort an Array of 0s, 1s and 2s

WHAT IT SAYS

You're given an array containing only the values 0, 1 and 2, and you have to sort it in place.

WHAT IT'S REALLY ASKING

"Sorted, this array is just three solid blocks. So stop asking 'is this element bigger than that one' and start asking 'which block does this element belong to, and can I grow the blocks inward until nothing is left unclaimed?'"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Hand it to a comparison sort

O(n log n) time, O(1) to O(n) space depending on the sort

Call sort(). It works. It has no idea the input is special, so it does what it always does: repeatedly ask pairs of elements which one is bigger, and shuffle them accordingly.

WHERE THE WORK IS WASTED — A comparison sort burns its entire budget discovering an ordering you were handed for free in the first line of the problem. Merge sort will compare a 1 against another 1 dozens of times, and every single one of those comparisons returns 'equal, do nothing'. Point at any comparison in the code: it is re-deriving the fact that 0 < 1 < 2, which you already knew before the array existed.

Count them, then rewrite the array

O(n) time in two passes, O(1) space

One pass to count how many 0s, 1s and 2s there are. Second pass to overwrite the array: c0 zeros, then c1 ones, then c2 twos. Linear, constant extra space, no comparisons at all.

WHERE THE WORK IS WASTED — Two passes is the cheap part. The real cost is that the second pass doesn't move elements, it manufactures them: it stamps out fresh 0s, 1s and 2s and throws the originals away. Harmless for bare integers, fatal the moment each element is an object that merely carries a 0/1/2 key, and impossible if you're only allowed to touch each element once.

KEY OBSERVATION — THE UNLOCKlink

Uncertainty is allowed to live in exactly one place

Picture the array as four regions in a row: settled 0s, settled 1s, an unknown middle, settled 2s. That's not a data structure, it's a claim about the array. It starts out trivially true — make the unknown middle everything and the other three empty. Now price a single element taken from the front of the unknown middle. If it's a 1, it is already standing on the border of the 1s block. The block absorbs it in place. Cost: nothing. If it's a 0, swap it with the first cell of the 1s block. What comes back? Something from inside the 1s block — which you have already proven is a 1. It lands at the front of the unknown middle and gets absorbed immediately. You never re-inspect it, because you already know what it is. If it's a 2, swap it with the last cell before the 2s block. What comes back? Something out of the unknown middle — an element nobody has ever looked at. You have learned nothing about it, so you must ask the question again. That asymmetry is the whole problem. Swapping leftward returns a known value; swapping rightward returns a stranger. Every off-by-one bug anyone has ever written here is somebody advancing the frontier after a rightward swap. And it has to terminate: each of the three cases shrinks the unknown middle by exactly one cell, so there are at most n cases. When the unknown middle is empty, the claim you've been maintaining the entire time is, word for word, the definition of a sorted array.

Three pointers, one pass

O(n) time, O(1) space, single pass — each element inspected once, plus one extra look for every 2

Keep low (the end of the 0s), high (the start of the 2s), and mid, the frontier of the unknown middle. Look only at a[mid]: on a 1, advance mid; on a 0, swap into low and advance both; on a 2, swap into high, pull high inward, and leave mid exactly where it is so the newcomer gets interrogated. Stop when mid crosses high — there is no cleanup pass, because the invariant already finished the sort while you weren't looking.

WHAT YOU TRADED — You trade stability and generality for that single pass: the swaps scramble the relative order of equal elements, and the trick only survives because k = 3 is known up front. At k categories you'd need k - 1 frontiers and the idea collapses back into counting sort. The transferable lesson: when the value space is tiny and known, stop comparing elements to each other and start comparing them to the value space.

WATCH THE IDEA RUN

0low / mid

7high

0s settled 0

1s settled 0

2s settled 0

unknown left 8

Nothing is settled. The unknown middle is the entire array, low and mid sit at the left wall, high at the right. The claim holds vacuously — now keep it holding.

step 1 / 10

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

The Shrinking Unknown

YOU'LL SEE IT AGAIN WHEN

The finished array is a handful of contiguous blocks whose order you already know before you start.
Elements fall into a tiny fixed set of categories, so 'compare' really means 'look up' — a comparison sort would just be re-deriving a ranking you were given.
The statement demands in-place / one pass / O(1) space, and doesn't care about order within a category.
You need to push things toward both ends at once, which means two write frontiers and a middle that shrinks.

SAME BLUEPRINT, DIFFERENT PROBLEM

Move ZeroesSort Array By ParityPartition ListHoare partition step (Quicksort / Quickselect)

The bar isn't "solved it once." It's "could rebuild it from the observation."