Longest Consecutive - Algorithm

Phase 1: Add all numbers to a hash set.

Phase 2: For each number $x$ in the set:

• If $x - 1$ is not in the set, $x$ is a sequence start
• Count consecutive numbers: $x, x+1, x+2, ...$ until not found
• Update the maximum length

Why is this $O(n)$?

Each number is the start of exactly one sequence. The inner counting loop visits each number at most once across all iterations. Time: $O(n)$. Space: $O(n)$.