Longest Consecutive Sequence

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Input / Output Format

Input: Array nums. Output: Length of longest consecutive run (integer).

Examples

Example 1

Input: nums = [100,4,200,1,3,2] → Output: 4 Explanation: Longest consecutive run is [1,2,3,4].

Example 2

Input: nums = [0,3,7,2,5,8,4,6,0,1] → Output: 9

Approach Hints

• Put all numbers in a hash set (O(n)).
• For each num in set, only start counting if num-1 is NOT in set (this is a streak start). Then walk forward num+1, num+2, ... while in set. Track max.
• Each element is visited at most twice → O(n).
• Pitfall: naive sorting gives O(n log n), failing the constraint.