A Harder Problem

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

Example: $[100, 4, 200, 1, 3, 2]$ Output: $4$ (the sequence is $[1, 2, 3, 4]$) The constraint: you must solve this in $O(n)$ time. Sorting would be $O(n \log n)$.

The trick here is subtle. Hash sets give $O(1)$ lookup, but how do you efficiently find consecutive sequences?