Longest Consecutive Sequence — Step-by-Step Visualization

Algorithm Pattern

Hash Set Intelligent Lookup

Key Idea

To achieve O(n) time, we can store all numbers in a HashSet. For each number `x`, we check if it is the start of a sequence by verifying that `x - 1` is NOT in the set. If it is the start, we increment to `x + 1, x + 2...` and track the length. This ensures each element is visited only a few times.

Step-by-Step Approach

1. Convert the array into a Set for O(1) lookups.
2. Iterate through the array.
3. For each number `n`, check if `n - 1` exists in the set.
4. If `n - 1` does NOT exist, `n` is the start of a sequence.
5. Keep checking for `n + 1, n + 2, ...` and count the length.
6. Update the maximum length found so far.

Common Gotchas

• Wait, isn't there a nested loop? Yes, but the inner loop only executes for the START of a sequence. Every number is part of exactly one sequence, so the total time complexity is O(n).