LeetCode 128 Longest Consecutive Sequence - Why Naive Fails

The obvious approach is to sort the array. After sorting [100, 4, 200, 1, 3, 2] becomes [1, 2, 3, 4, 100, 200]. Then scan for consecutive runs.

Sorting works, but it's $O(n \log n)$. The problem explicitly asks for $O(n)$.

You need a way to find consecutive sequences without sorting. What data structure gives $O(1)$ lookups to check if a number's neighbors exist?