LeetCode 128 Longest Consecutive Sequence - Example and Complexity Analysis

Walk through nums = [9, 1, 4, 7, 3, 2, 6, 5, 8] step by step.

First, build the set: {1, 2, 3, 4, 5, 6, 7, 8, 9}.

Check each number. Is num - 1 in the set?

• 9: Is 8 in set? Yes. Skip.
• 1: Is 0 in set? No. This is a sequence start.
• 4, 7, 3, 2, 6, 5, 8: All have predecessors. Skip.

From 1, count up: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9. Length = 9.

Each number is visited at most twice: once to check if it's a start, once during counting from some start. That's $O(n)$ time.

The hash set stores $n$ elements, so $O(n)$ space.