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.
Playground, this isn't a screenshot
values 1…4 placed at index value − 1
3
i=0
1
i=1
2
i=2
4
i=3
3 belongs at index 2. Swap with what is there
2
i=0
1
i=1
3
i=2
4
i=3
2 belongs at index 1. Swap again
1
i=0
2
i=1
3
i=2
4
i=3
1 is home. Move on. Everything is in place

Green 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