Longest Consecutive Sequence
Longest Consecutive Sequence is a medium Arrays & Hashing problem from the Blind 75. The key pattern is hash set run starts, and a good solution runs in O(n) time.
Problem
Return the length of the longest run of consecutive integer values in an unsorted array.
Examples
Example 1
Input
[12,4,7,5,6,20]Output
4Example 2
Input
[]Output
0Example 3
Input
[50,3,90,1,4,2]Output
4Approach
Put every value in a set. Only start counting at values whose predecessor is missing, then extend upward while the next value exists.
| Pattern | Hash set run starts |
|---|---|
| Time | O(n) |
| Space | O(n) |
Watch out for
Duplicates must not extend a run; the set removes them.