Longest Consecutive Sequence
Only start counting from a number that has no left neighbor.
Run Trace
Problem
Given an unsorted array of integers, determine the greatest number of distinct values that can be arranged into a consecutive run. The run may begin at any value, and the input can contain duplicates. Return only the length of the longest run.
Examples
Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Input: nums = [9, 1, 4, 7, 3, 2, 6, 5]
Output: 7
The Goal
Return the length of the longest run of consecutive integers in nums, in any order: values like x, x + 1, x + 2.
For [100, 4, 200, 1, 3, 2], the run is 1, 2, 3, 4, so the answer is 4.
Sorting finds it in O(n log n). A hash set finds it in O(n).
Values, not positions
A run is made of values that differ by 1. Where they sit in the array doesn't matter.
1, 2, 3 and 4 form a run even though 4 comes first.
Key Idea: Count Only From a Run's Start
Put every number in a set, so checking x in values takes constant time.
A number x starts a run only if x - 1 isn't in the set. If it is, x sits inside a run that starts lower, and counting from x would repeat work.
From each start, step up through x + 1, x + 2 and so on until a number is missing.
x starts a run when x - 1 isn't in the set.
1 starts: 0 is missing.
The Algorithm
values = set(nums)
best = 0
for x in values:
if x - 1 not in values:
current, length = x, 1
while current + 1 in values:
current += 1
length += 1
best = max(best, length)
return bestThe inner loop looks nested, but each number is stepped onto at most once, by the walk from its own run's start. So the whole thing is O(n).
| Approach | Time | Space | How |
|---|---|---|---|
| Set, count from starts | O(n) | O(n) | Each run walked once |
| Sort, then scan | O(n log n) | O(1) to O(n) | Neighbors end up side by side |
| Walk from every number | O(n^2) | O(n) | Walks the same run again |
Walkthrough
Run it on [100, 4, 200, 1, 3, 2]. A set has no order of its own, so the stage takes the numbers in the order they first appear.
100 and 200 start runs of length 1. 4, 3 and 2 are skipped, since each has its left neighbor in the set. 1 starts a run, and the walk finds 2, 3 and 4 before 5 is missing. The best is 4.
Only three numbers start a walk.
Checkpoint · predict the next step
Step 7 of 20 on the stage: 199 isn't in values, so 200 starts a run.
values = {100, 4, 200, 1, 3, 2} · x 200 · best 1
Pitfalls
- Check
x - 1before walking. Walking from every number walks a run once per member:O(n²)on one long run. - Loop over the set, not
nums. With repeats, each copy of a start would walk its run again. - Duplicates count once:
[1, 2, 2, 3]gives 3. - An empty list returns 0, since
beststarts there.
In the set {1, 2, 3, 4, 100}, which number starts the walk of length 4?
Complexity
Building the set is O(n). Each number is checked as a start once, and stepped onto by a walk at most once more. That's O(n) time on average.
The set holds up to n numbers, so extra space is O(n).
A set, and one walk per run
- Build the setOne insert per number.dominantO(n)
- Start checksOne per number.dominantO(n)
- WalksEach number joins one walk.dominantO(n)
- The setUp to one entry per number.dominantO(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Each run is walked once, from its start.
In short
Put everything in a set for O(1) lookups. For each value, only begin a run if value − 1 is absent (it's the start of a streak), then walk value+1, value+2, … counting length. Every element is visited at most twice, giving O(n) despite the nested look.
Common mistake
Sorting (O(n log n)) — acceptable, but it misses the intended O(n) set-based trick that starts only from run beginnings.