LeetCode #128 — Longest Consecutive Sequence, Walked Through the Six-Phase Framework

Longest Consecutive Sequence asks for the longest run of consecutive integers in an unsorted array, in O(n) time. Sorting takes O(n log n), so we can't sort. The trick: **start a run only from a number that has no predecessor in the set**. That single observation collapses what looks like an O(n²) problem into a clean linear scan. Longest Consecutive Sequence is the **start-of-run** problem. The hashset gives O(1) membership; the trick is recognizing that you should only expand from numbers without predecessors. That single observation collapses an apparent O(n²) into a clean O(n). **The pattern transfer: when computing something over runs/groups in unordered data, find a way to identify each group exactly once — usually by checking whether you're at the "start" or "canonical representative" of that group.** This generalization shows up in flood-fill (visit each component from one seed), union-find (each component has one root), and many graph problems. ---