Pattern Recognition Drill
Medium Sorting
The Problem
Sort an array of 0s, 1s, and 2s in one pass.
What approach would you use?
Think about it before scrolling down.
lo/mid/hi pointers. Swap 0s to lo, 2s to hi, skip 1s. One pass, O(n) time, O(1) space.
Counting sort (count 0s, 1s, 2s, overwrite) also O(n) but requires two passes.
Common Trap
General sorting is O(n log n). This is a special case with only 3 values → can do O(n).