Why it works
- Every chain has one start: the number with no x − 1 in the set. A number with x − 1 there sits inside someone else's chain, so it is skipped at once.
- From a start the chain is counted upwards, x + 1, x + 2, while the set has the next number. The set answers each of these questions in one step.
- So each number is stepped on at most once inside a chain, and the loop inside the loop still makes O(n) steps in total.
Complexity
Time O(n): set lookups are O(1) on average, and each number is counted in at most one chain. Sorting first would take O(n log n). Memory O(n) for the set.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗