Longest Consecutive Sequence
Medium · rating 1550 · Hashing
The first line has n. The second line has n integers (unsorted, possibly with duplicates). Print the length of the longest run of consecutive integers present (order doesn't matter).
For 100 4 200 1 3 2 the answer is 4 (1,2,3,4).
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Put every value in a hash set. A number starts a run only if its predecessor is absent, so from each such start, walk upward while the next value exists and measure the streak. Non-start numbers are skipped, keeping it linear.
Why it isn't quadratic
Each value is walked over at most once — only as part of the single run that begins at its smallest member.
for x in s:
if x - 1 not in s:
y = x
while y + 1 in s: y += 1
best = max(best, y - x + 1)Complexity
Time: O(n). Space: O(n).
Related problems
- Partition Labels — Medium
- Subarrays Divisible by K — Medium
- Longest Substring Without Repeats — Medium
- Subarrays Summing to K — Hard
- Count Anagram Groups — Medium
- Count Pairs With Difference — Medium