Longest Consecutive Sequence

mediumArrays & Hashing+20 XPTime limit 2s

Find the length of the longest run of consecutive integers (like 4, 5, 6, 7) that can be formed from the values in the array. The values may be in any order and may repeat.

Input:

line 1: n
line 2: n integers

Output: the length of the longest consecutive run.

Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹.

Challenge: sorting gives O(n log n). Can you do O(n) with a hash set — only starting to count from numbers x where x − 1 is not in the set?

Sample input 1

6
100 4 200 1 3 2

Sample output 1

Sample input 2

10
0 3 7 2 5 8 4 6 0 1

Sample output 2

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…