You're handed a pile of integers in no particular order — nums. Hidden inside it, values may chain together into consecutive runs: 1, 2, 3, 4 counts as a run even when those numbers are scattered all over the array.
Return the length of the longest consecutive run of values that all appear in nums. Positions don't matter, duplicates count once, and an empty array has a longest run of 0.
The catch: your algorithm must run in O(n) time — sorting first won't meet the bar.
O(n) bound rules it out. What structure answers does value x exist in O(1)?x starts a run exactly when x - 1 is absent — walk forward only from starts, and every run gets traversed once, for amortized O(n).[1, 0, 1, 2] has values 0, 1, 2, so the answer is 3.num - 1 guard ensures each run is walked exactly once, so the total walk steps across the entire loop are at most n — amortized O(n).0 — there is no run at all. Make sure your best-so-far starts at 0, not 1.O(n) — in an interview, the hash-set solution is the expected answer, with sorting as your warm-up.start, start + 1, …, start + len - 1. Same complexity.x, merge the run ending at x - 1 with the run starting at x + 1 and update both new endpoints. Each insert is O(1) average.x starts a group when none of x - 1 … x - k are present, and walks may jump gaps up to k. With large sparse values, sorting or bucketing becomes the practical choice.x with x + 1, and to an endpoint-merging hash map — three different data structures, one shared insight: only the boundaries of a run matter.Input: nums = [100,4,200,1,3,2] Output: 4 The longest consecutive run is `[1, 2, 3, 4]` — its length is 4.
Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9 Every value from `0` through `8` appears, forming a run of length 9.
Input: nums = [1,0,1,2] Output: 3 The values `0, 1, 2` appear; the duplicate `1` counts once, so the answer is 3.
- 0 <= nums.length <= 10^5 - -10^9 <= nums[i] <= 10^9
Sorting cracks this problem in a minute — but the statement dares you to do better: find the longest run of consecutive values in O(n), in an array with no order at all. The idea that makes it possible — only count a streak from its first element — is one of the most reusable tricks in hashing problems.
O(1) average time — the engine that replaces sorting here.O(n).O(n log n) approach makes it clear what the O(n) requirement is really testing.Formally: given an integer array nums (possibly empty, possibly with duplicates), return the length of the longest run of consecutive integers — v, v+1, v+2, … — such that every value of the run appears somewhere in nums. Positions are irrelevant, duplicates count once, and an empty array returns 0.
Worked example 1 — nums = [100, 4, 200, 1, 3, 2]
values present: {1, 2, 3, 4, 100, 200}
1 → 2 → 3 → 4 run of 4 ✓ longest
100 run of 1
200 run of 1
answer: 4
Worked example 2 — nums = [1, 0, 1, 2]
values present: {0, 1, 2}
0 → 1 → 2 run of 3 (the duplicate 1 adds nothing)
answer: 3
Two minutes of questions saves you from solving the wrong problem — and shows the interviewer you read inputs like a senior engineer.
“Can nums contain duplicates?”
Yes — and they must count once. A streak counter that treats a duplicate as a break (or as progress) returns the wrong length on inputs like [1, 0, 1, 2].
“Can values be negative or very large?”
Yes — anywhere in ±10^9. That rules out a counting array indexed by value; you need a hash-based structure.
“What does an empty array return?”
0 — there is no run at all. Initialize your best answer to 0, not 1.
“Does consecutive mean adjacent positions in the array?”
No — it means values differing by exactly 1, wherever they sit. [100, 4, 200, 1, 3, 2] contains the run 1, 2, 3, 4.
“How large is n, and is O(n log n) acceptable?”
n reaches 10^5. Sorting would run fast enough in practice, but the statement explicitly demands O(n) — the interviewer wants the hash-set idea.
Before I code, let me confirm the rules of the game.
Consecutive means values differing by one anywhere in the array, not adjacent positions — correct?
Duplicates count once, and an empty array should return zero.
Since the bound is O of n with values up to a billion, I am thinking hash set rather than sorting.
The run 1, 2, 3, 4 exists whether the array is sorted or scrambled. The only question the algorithm ever asks is: does value x exist? A hash set answers that in O(1) — so tip everything into a set and forget the array order entirely. Duplicates collapse for free.
run: 1 → 2 → 3 → 4
^
1 is the start, because 0 is absentA value x starts a run exactly when x - 1 is not in the set. That is a one-lookup test — cheap enough to run on every element.
Walk forward from every element and an all-consecutive array like 1..n costs O(n²) — element 1 walks n steps, element 2 walks n - 1, and so on. But if only starts walk, each run is traversed exactly once. Every element is touched at most twice — once by its start-check, once inside its run's single walk — so the nested loops sum to O(n).
| Brute force | Sorting | Hash set | |
|---|---|---|---|
| Time | O(n³) | O(n log n) | O(n) |
| Space | O(1) | O(n) | O(n) |
The full code for each approach — with traces and pitfalls — lives in the Approaches selector below.
Key takeaway
When a problem cares about which values exist rather than where they are, trade sorting for a hash set — and when measuring runs, only walk from elements whose predecessor is absent. Start-detection turns a nested loop into amortized O(n).
seen = hash set of nums
best = 0
for num in seen:
if num - 1 in seen: skip # not a run start
walk k = 1, 2, … while num + k in seen
best = max(best, run length)
return best