Longest Consecutive Sequence

Problem

Given an unsorted array nums, return the length of the longest run of consecutive integer values (positions in the array don't matter). You must run in O(n).

Examples

Constraints

0 ≤ n ≤ 10⁵ · values in ±10⁹ · O(n) required.

Attempt it first

This is the module capstone: the required O(n) is the entire puzzle. The obvious good solution — sort, scan for runs — is O(n log n), and the problem explicitly bans it. Sit with it for a while; the trick is a new kind of move, and meeting it cold is worth real struggle.