Longest Consecutive Sequence
WHAT IT SAYS
Given an unsorted array of integers, find the length of the longest run of consecutive numbers that can be assembled from its values.
WHAT IT'S REALLY ASKING
"Every run has exactly one true beginning. So stop asking 'how long is the run through x?' and ask the cheap question first: does x-1 exist? If it does, x is somebody else's middle — not your problem."
Grow a chain from every element
O(n^3) time in the worst case, O(1) extra spaceFor each value x, look for x+1 in the array; if it's there, look for x+2, and keep going until the chain breaks. Track the longest chain you managed to build.
WHERE THE WORK IS WASTED — Two distinct redundancies stacked on top of each other. First, every 'is x+1 present?' is answered by a full linear rescan of the array, re-reading n elements to check one membership fact. Second — the deeper one — a run of length k gets walked from all k of its members: you build 5,6,7,8 starting from 5, then rebuild 6,7,8 starting from 6, then 7,8, then 8. The same chain is traversed k times to learn the same thing, and only the first walk was ever going to produce the winning answer.
Sort, then scan for runs
O(n log n) time, O(1) or O(n) space depending on the sortSort the array, then sweep once: consecutive values extend the current run, duplicates are skipped, a gap resets it. Simple and easy to get right.
A number with a predecessor is nobody's starting line.
Sorting is overkill: it hands you a total ordering when the only thing you ever ask is 'is this specific value present?' — a question a hash set answers in O(1) without knowing anything about order. So the rescanning problem is solved. But that only kills the first redundancy; the chain-rebuilding is still there, and a naive 'expand from every x' over a hash set is still quadratic on input like 1..n. Here's the fix. Partition the values into maximal runs. Each maximal run has exactly ONE element x whose predecessor x-1 is absent from the set — the run's true head — and by definition the run cannot be extended leftwards past it. Every other member of that run has x-1 present, which means it sits strictly inside a chain someone else already owns. Expanding from it can only re-derive a suffix of a walk the head will do anyway. So guard the expansion: only walk forward from x when x-1 is NOT in the set. Now count the total work. Each run is walked exactly once, and the walk visits each of its members once — so across all runs the forward-stepping does at most n steps in total, ever. The inner while loop looks quadratic and is not; the guard is what pays for it. That's an amortisation argument, and without the guard the argument fails.
Set membership, expand only from heads
O(n) expected time, O(n) space — each element is a start-check once, and a walk-step at most onceDump every value into a hash set (duplicates collapse for free). For each value x, check whether x-1 is in the set; if it is, skip x entirely. If it isn't, x is a run head, so walk x+1, x+2, ... while they're present and measure how far you get. The largest such walk is the answer.
Only Expand From Heads
YOU'LL SEE IT AGAIN WHEN
- You're asked about runs, chains or groups that can be assembled from a set, and order within the input is irrelevant.
- The only question you keep asking the data is 'does this exact value exist?', never 'what is bigger than this?' — membership, not comparison.
- The obvious expand-from-everywhere loop redoes the same traversal once per member, so there is a canonical representative (a head, a root, a boundary) you could expand from instead.