visual walkthrough
Longest Consecutive Sequence
Starting only from sequence beginnings gives O(n); a classic 'think before you sort' problem.
The idea
Sorting makes consecutive numbers neighbours, but costs O(n log n). With a set you can skip the sort: a number only starts a run if the number just below it is missing, and from a start you walk upwards.
Every number is walked over at most once, so the total work stays linear.
Complexity
| approach | time | space |
|---|---|---|
| Sort and scan | O(n log n) | O(n) |
| Hash set | O(n) | O(n) |