Find the length of the longest run of consecutive integers in an unsorted list in O(n) using a set and run-start detection. Classic FAANG-style question.
The problem
Return the length of the longest run of consecutive integers that can be formed from the values in nums (in any order). Duplicates count once.
[100, 4, 200, 1, 3, 2] → 4 (the run 1, 2, 3, 4). Aim for O(n) — no sorting.
Examples
Example 1
Input
longest_consecutive([100, 4, 200, 1, 3, 2])
Expected output
4
Example 2
Input
longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])
Expected output
9
+ 4 hidden tests on Submit — duplicates count once.
Edge cases to ask about
- Empty list
- Duplicates
- Negative numbers
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Sort, then count runs | O(n log n) | O(n) | Simple and correct. |
| bestSet + only count from run starts | O(n) | O(n) | A value starts a run if value − 1 is absent; each value is walked at most twice. |
Walkthrough of the optimal approach (try it yourself first)
Put everything in a set. Only begin counting at a value whose predecessor x - 1 is absent — that is a run start. From there, walk x + 1, x + 2, … while present.
It looks like a nested loop, but each value is part of exactly one run and is walked only from that run's start, so the total inner work across all starts is n. That amortised argument is what the interviewer wants to hear.
Complexity: O(n) time, O(n) space. Each value is the start of at most one inner walk, and every value is visited by at most one walk — so the total work is linear despite the nested loop.
Reveal the reference solution
def longest_consecutive(nums): values = set(nums) best = 0 for x in values: if x - 1 not in values: # x starts a run length = 1 while x + length in values: length += 1 best = max(best, length) return best
The brute force, for comparison
def longest_consecutive(nums): if not nums: return 0 s = sorted(set(nums)) best = run = 1 for a, b in zip(s, s[1:]): run = run + 1 if b == a + 1 else 1 best = max(best, run) return best
Follow-ups interviewers ask
- Return the sequence itself.
- Explain why the nested loop is still O(n).
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Longest Consecutive Sequence in Python?
The optimal solution runs in O(n) time and O(n) auxiliary space. Each value is the start of at most one inner walk, and every value is visited by at most one walk — so the total work is linear despite the nested loop.
What is the brute-force approach, and how do you optimise it?
Sort, then count runs: O(n log n) time, O(n) space. Simple and correct. Set + only count from run starts: O(n) time, O(n) space. A value starts a run if value − 1 is absent; each value is walked at most twice.
What follow-up questions do interviewers ask about Longest Consecutive Sequence?
Return the sequence itself. Explain why the nested loop is still O(n).