Longest Consecutive Sequence
Given an unsorted array, return the length of the longest run of consecutive integers (in O(n) time).
Open on LeetCode ↗Intuition
Sorting would solve it but costs O(n log n). Instead, dump everything into a set for O(1) membership. Only start counting a run from its true beginning — a number whose predecessor is absent — so each run is walked exactly once.
Approach
Sorting solves it — but it's too slow
If you sort, consecutive numbers line up and you can scan for the longest run. Correct, but sorting is O(n log n), and this problem explicitly wants O(n). So we need the grouping benefit of sorting without paying to sort. A hash set gives us O(1) membership checks, which is the tool that replaces sorting here.
Only walk a run from its true beginning
Drop every number into a set. The danger is double-counting: if we tried to grow a run from every number, a length-k run would be walked k times, ballooning to O(n²). The fix is a guard — a number n is only the start of a run if n − 1 is absent from the set. That condition is true for exactly one number per run, so each run is discovered once and walked once.
Extend forward and total it up
From a confirmed start n, keep checking n+1, n+2, … in the set, counting length until the chain breaks, and track the maximum. Because the expensive walking only fires at run-starts, the combined length of all walks is at most n — so even with the outer loop, total work is O(n). Duplicates collapse harmlessly in the set; an empty array yields 0.
Solution & live demo
Edge cases
The set collapses duplicates, so a repeated value neither lengthens nor restarts a run.
The loop never runs; best stays 0.
Each lone number is its own run of length 1 because its neighbor is absent.