Given an unsorted array of integers, return the length of the longest sequence of consecutive values, such as 1, 2, 3, 4. Your solution must run in O(n) time.
Before you code
Sorting gives O(n log n). For O(n), put every value in a hash set, so "is x + 1 present?" costs O(1) on average. The trap is walking a run from every element in it, which is O(n²) on an input like 1, 2, …, n.
Hints
- Only start counting at
xifx - 1is not in the set: that makesxthe first value of its run. - From a run's start, count upward while
x + 1is in the set. - Each value is visited at most twice, once in the main loop and once while counting its run, so the total is O(n).
- Duplicates don't matter, because the set removes them.
Production & complexity notes
When solving Longest consecutive sequence on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Hash maps in your language to reinforce the underlying pattern.
What it practices
Using a hash set as an O(1) membership test, from Hash maps in your language.