0
Challenge · 34Sort & Search
Cyclic sort and index as hash
Patternsused in ~70% of apps
The pattern that answers a question you should have been asking: why does a problem bother telling you the values are between 1 and n? Because that sentence is the algorithm.
Core idea. When the values are a bounded range of positions, the array can be its own lookup table. Value v belongs at index v − 1. Put every value where it belongs, and whatever is out of place afterwards is the answer, with no extra memory at all.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
values 1…4 placed at index value − 1
3
i=01
i=12
i=24
i=32
i=01
i=13
i=24
i=31
i=02
i=13
i=24
i=3Green means "value v is sitting at index v − 1". Once everything is green, any remaining mismatch is the answer. A missing value, a duplicate, or both.
↑ play a little first, then dig in