LeetCode 128 Longest Consecutive Sequence - Solution

Put all numbers in a hash set. The set gives $O(1)$ lookup to check if any number exists.

The trick: only start counting from sequence beginnings. A number starts a sequence if num - 1 is NOT in the set. If num - 1 exists, then num is part of an earlier sequence, so skip it.

For each sequence start, count upward: check if num + 1 exists, then num + 2, and so on until you hit a gap.

With nums = [100, 4, 200, 1, 3, 2], the set is {1, 2, 3, 4, 100, 200}. You check each number: is num - 1 in the set? Only 1, 100, and 200 pass this test. From 1, you count up to 4. That's your longest sequence.