Cyclic Sort
When values are 1..n, each value names its own index — sort in O(n) and find missing or duplicate numbers in O(1) space.
This topic is part of Pro.
Free covers the C and Python courses, the first three DSA topics, the opening system design lessons and the beginner AI lessons, all with the full coach. Pro opens the rest of the library in the FollowtheDamnCode app.
What is in it
- 1Every value has a homeSwap each value to index value − 1 until the right value sits at the current index — O(n) total swaps. Pro
- 2Finding missing numbersAfter placing every value at home, the slots holding the wrong value reveal what's missing. Pro
- 3Finding duplicatesA value with nowhere to go is a duplicate — or, without modifying the array, follow value-as-pointer cycles. Pro