Longest Consecutive Sequence

Problem Given an unsorted integer array, return the length of the longest run of consecutive integers (values, not positions).

Input / Output

• Input: int array nums. Output: longest consecutive-run length.

Constraints

• n up to 10^5; O(n) required — sorting (O(n log n)) is the explicit thing to beat.

Example

• [100,4,200,1,3,2] → 4 (1,2,3,4); [0,3,7,2,5,8,4,6,0,1] → 9.

Expected approach

• HashSet of all values; only start counting from run beginnings — values v where v−1 is absent — then extend v+1, v+2, … Each value is visited O(1) times amortized → O(n). The run-start guard is what makes it linear; without it the loop is O(n^2). Duplicates are absorbed by the set. Union-Find is a heavier O(n α) alternative worth naming.