Longest Consecutive Sequence

Difficulty: Hard · Topic: Hashing

Given an unsorted array nums, return the length of the longest run of consecutive integers (e.g. [100,4,200,1,3,2] → 4 for 1,2,3,4). Sorting would be O(n log n); a hash set gets you to O(n).

Examples

longest_consecutive([100,4,200,1,3,2])
→ 4

The run 1,2,3,4 has length 4.

longest_consecutive([0,3,7,2,5,8,4,6,0,1])
→ 9

Target complexity: time O(n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.