Longest Consecutive Sequence
Find the longest run of consecutive integers hidden in an unsorted array, in linear time. A hash set lets you start counting only at the beginning of each run. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an unsorted array of integers nums. Find the length of the longest sequence of consecutive integers x, x + 1, x + 2, ... whose values all appear somewhere in nums. The values can be in any positions; they don't have to be next to each other in the array.
Duplicates count only once. Return 0 for an empty array.
Aim for O(n) time.
Example 1
- Input
- nums = [10, 4, 12, 11, 3, 5, 13, 30]
- Output
- 4
10, 11, 12 and 13 are all present. The run 3, 4, 5 is shorter.
Example 2
- Input
- nums = []
- Output
- 0
Example 3
- Input
- nums = [7, 7, 8, 8, 6]
- Output
- 3
The run is 6, 7, 8. The repeated 7 and 8 don’t make it longer.
Constraints
- 0 ≤ nums.length ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Longest Consecutive Sequence in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Longest Consecutive Sequence
Pattern: Hash set, count from run starts
Sorting would line the runs up, but it costs O(n log n), and the problem asks for O(n). What sorting really gives you is "what comes next after x?", and a hash set answers is x + 1 present? in O(1) without any ordering.
The catch is avoiding repeated work. If you count upward from every number, a run of length L gets counted from each of its L members, which is quadratic on one long run. So only count from a number that starts a run: one where x - 1 is not in the set. Every run then has exactly one starting point, and each number is visited at most twice overall: once in the outer loop, once while extending its run.
Approach 1: Brute force: extend from every number
For each number, check x + 1, x + 2, ... with a linear scan of the array each time. With a run of length n this is n starting points, each extending up to n steps, each step scanning n elements.
Time O(n³) · Space O(1)
Approach 2: Sort and scan
Sort, then walk the array once. Skip equal neighbors, extend the current run when the next value is exactly one more, and reset otherwise. Simple and uses little memory, but sorting is O(n log n).
Time O(n log n) · Space O(1) to O(n), depending on the sort
Approach 3: Hash set, count only from run starts
- Put every number into a set. This also removes duplicates.
- For each
xin the set, skip it ifx - 1is in the set, because it isn't the start of a run. - Otherwise count upward: while
x + lengthis in the set, increaselength. - Track the longest length seen.
The inner loop only runs from run starts, and the runs don't overlap, so all inner steps add up to at most n.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Brute force: extend from every number | O(n³) | O(1) |
| Sort and scan | O(n log n) | O(1) to O(n), depending on the sort |
| Hash set, count only from run starts | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Longest Consecutive Sequence solution in Python
def longest_consecutive(nums: list[int]) -> int:
values = set(nums)
best = 0
for x in values:
if x - 1 in values:
continue # not the start of a run
length = 1
while x + length in values:
length += 1
best = max(best, length)
return bestLongest Consecutive Sequence solution in JavaScript
function longestConsecutive(nums) {
const values = new Set(nums);
let best = 0;
for (const x of values) {
if (values.has(x - 1)) continue; // not the start of a run
let length = 1;
while (values.has(x + length)) length++;
best = Math.max(best, length);
}
return best;
}Common mistakes
- Counting upward from every number instead of only from run starts, which is O(n²) on one long run like 0..99999.
- Iterating over the original array instead of the set. With many duplicates of a run start, you redo the same run once per copy.
- Counting duplicates as part of the run length when sorting, for example treating [6, 7, 7, 8] as length 4.
- Returning 1 instead of 0 for an empty array.
What interviewers look for
Sorting is a fine first answer; say it and its cost, then point out that the O(n) requirement rules it out. The interviewer is waiting to hear two things: that a set replaces "look at the next sorted value" with a constant-time membership check, and why the start-of-run check keeps it linear.
Make the amortized argument explicitly: "each number is touched by the inner loop at most once, because it belongs to exactly one run." Without it, the nested loop looks quadratic and you may get pushed on it.
Follow-up questions
What if numbers are added one at a time and you must report the longest run after each insertion?
Use a union-find keyed by value, or a hash map that stores run length at the two endpoints of each run. When x arrives, look up the runs ending at x - 1 and starting at x + 1, merge them, and update only the new endpoints. Each insertion is near O(1).
How would you return the run itself rather than its length?
Store the starting value along with the best length. The run is then start, start + 1, ..., start + length - 1.
What if memory is tight and you can modify the array?
Sort in place with an O(1)-space sort like heapsort, then scan. You give up linear time for constant extra space.
Companies that ask Longest Consecutive Sequence
Longest Consecutive Sequence is tagged by 126 companies in our interview dataset. The score shows how often it comes up at each company.
- Corelight100%
- Surveymonkey100%
- Resmed100%
- Wissen Technology100%
- Gopuff97%
- Personio95%
- Zepto93.7%
- Sourcegraph91%
- Daimler91%
- Shipt91%
- Weave86%
- Check Point Software Technologies83%
- Epic Games82%
- Fico82%
- Okta81.6%
- L3harris80%
- Micron Technology80%
- Sojern78%
- Mx78%
- Transunion77%
- Paytm76.6%
- Turnberry Solutions76%
- Ihs Markit75%
- Fdm Group74%
and 102 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required