Set-start expansion

40 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

The numbers 100, 4, 200, 1, 3, 2 are given in a jumble, and the question is: what is the longest run of consecutive integers hiding in there? The run 1, 2, 3, 4 has length 4, so the answer is 4.

The obvious plan is to sort first: 1, 2, 3, 4, 100, 200, then walk along and count how long each run of "next is previous plus one" lasts. That is correct and costs O(n log n) for the sort. The interview version of the question asks for O(n), so sorting is exactly what we are trying to avoid. Without sorting, the by-hand idea is: take each number x, ask whether x + 1 is in the list, then x + 2, and so on. Each "is it in the list" is a scan, and worse, you count the same run again and again starting from each of its members.

Build the structure, one piece at a time

Piece one: put every number into a hash set, so "is x + 1 present?" costs about one step. The set for our example is {100, 4, 200, 1, 3, 2}.

Piece two, the actual idea: do not start counting from every number. Start only from numbers that begin a run, which are the numbers x where x − 1 is not in the set. A number whose predecessor exists is in the middle or at the end of a run, and that run will be counted when its true start is visited.

Walk the numbers in any order and apply the rule:

Only three numbers started a count, and the run 1 … 4 was walked exactly once, from its start.

Why it is correct

Every run of consecutive integers has exactly one smallest member, and that member is the only one whose predecessor is absent from the set. So every run gets counted exactly once, from its smallest member, and the count up (while x + 1, x + 2, … are present) reaches exactly the largest member. Taking the maximum over all run starts therefore gives the longest run. No run is missed, because its start is in the list, and no run is overcounted, because non-starts are skipped.

Why it is fast

Here is the counting argument that makes this O(n) and not O(n²). Each number is looked at once as "is it a start?" That is n set lookups. Each number is also visited at most once inside a count-up, because a count-up only walks the members of one run, and each run is walked once. So the count-ups together do at most n more lookups. In total:

lookups ≤ n (start checks) + n (count-up steps) = 2n

Each lookup is about one step, so the time is O(n), with O(n) memory for the set. Had we counted up from every number, the run 1 … k alone would cost 1 + 2 + … + k = k(k + 1)/2 steps, which is quadratic.

How to recognise it in an interview

Cues: "longest consecutive", "unsorted", "O(n) required". The moment the interviewer rules out sorting, this is the pattern.

Say: "I will put the numbers in a set and only expand runs from numbers whose predecessor is absent, so each number is touched at most twice." That is the full solution to Longest Consecutive Sequence. In Binary Tree Longest Consecutive Sequence the same "only extend from where the previous value is missing" idea appears, except the neighbours come from parent and child instead of a set.

02The idea in one line

Only start a run from numbers whose predecessor is absent.

Reach for it when: Longest consecutive sequence in unsorted data.

Cost: O(n) time, O(n) space.

03The walk-through, step by step

The video works one example: Longest Consecutive Sequence on [100,4,200,1,3,2]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Put everything in a set; only start a run where x−1 is absent
2. 100 starts a run: count up while present → length 1
3. 4: 3 is in the set, so 4 is not a run start, skip
4. 200 starts a run: count up while present → length 1
5. 1 starts a run: count up while present → length 4
6. 3: 2 is in the set, so 3 is not a run start, skip
7. 2: 1 is in the set, so 2 is not a run start, skip
8. Longest run: 1,2,3,4 → 4
9. Each number is checked at most twice: O(n) with a set

04Asked at Google

2 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Arrays & Hashing: Hash the complement, Frequency counting, Canonical key hashing, In-place index hashing, Seen-set cycle detection.