LeetCode 128 Longest Consecutive Sequence - Problem Statement

LeetCode 128 Longest Consecutive Sequence gives you an unsorted array of integers. Find the length of the longest consecutive elements sequence.

For example, nums = [100, 4, 200, 1, 3, 2] returns 4 because the sequence [1, 2, 3, 4] has four consecutive numbers.

Here's the challenge: you need $O(n)$ time. Sorting would work but takes $O(n \log n)$. How can you identify consecutive sequences without sorting?

Constraints: $0 \le n \le 10^5$, values from $-10^9$ to $10^9$.