The problem
Given an unsorted list of numbers, find the length of the longest run of consecutive numbers (like 1, 2, 3, 4). The run can be made from numbers anywhere in the list.
Input: [9, 4, 1, 3, 2, 10, 15, 4] Output: 4 (the run 1, 2, 3, 4)
Picture it
Imagine numbered beads spilled onto a ruler, each landing at its own number. A run is a row of beads with no gaps. We only start counting at a bead that has no bead just before it (it is the start of a run), then walk right while the next bead exists. That way every run is counted once.
How to recognise it
- You need runs of consecutive values (x, x + 1, x + 2, ...), but the values can sit anywhere in the list.
- The positions do not matter, only which values exist. That points to a set.
- The problem asks for O(n) time, which rules out sorting (O(n log n)).
- Up to 10^5 numbers between −10^9 and 10^9, so you cannot use the values as list indices.
Start with brute force
From every number x, count upwards for as long as the next value is in the list.
def longest_consecutive_brute(nums):
best = 0
for x in nums:
length = 1
while x + length in nums: # list search: O(n) each time
length += 1
best = max(best, length)
return best
Each in on a list scans it, so one run of length L costs O(L · n), and doing it from every start gives O(n³) in the worst case (one long run). With n = 10^5 that is hopeless: even a single scan from every start, 10^10 steps, is too slow. Space is O(1).
Sorting first and then counting runs of neighbours works in O(n log n), but the problem asks for O(n).
From brute force to the idea
- Make lookups fast. Put the numbers in a set, so
x + 1 in sis O(1) on average. That alone gives O(n²) for one long run, because every number in the run counts the rest of it again. - Find the waste. In the run 1, 2, 3, 4, counting from 2, 3 and 4 only repeats part of the count from 1.
- Only count from the start of a run. x starts a run exactly when x − 1 is not in the set. Every other number is in the middle of someone else's run, so skip it.
- Walk the run. From a start, step up while
x + lengthis in the set, then compare with the best. - Loop over the set, not the list. Duplicates then appear once, so no run start is counted twice.
This is the key idea: a set for O(1) lookups, and counting only from numbers with no left neighbour.
The key idea
Put everything in a set. Only start counting from numbers whose (x − 1) is missing. Each number is visited a constant number of times: O(n).
Python solution
def longest_consecutive(nums):
s = set(nums)
best = 0
for x in s:
if x - 1 not in s: # x starts a run
length = 1
while x + length in s:
length += 1
best = max(best, length)
return bestIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n³) worst case: each step of each run scans the whole list | O(1): a few counters |
| Set + run starts (shown code) | O(n): the while loop only runs from run starts, so each number is stepped over once | O(n): the set |
The inner while looks like it could make this O(n²). It cannot: the runs do not overlap, and their lengths add up to at most the number of distinct values.
Edge cases
- Empty list: the set is empty, the loop never runs, and the answer is 0.
- One number: returns 1.
- Duplicates (
[1, 2, 2, 3]): returns 3. The set removes the extra 2. - All equal (
[5, 5, 5]): returns 1. - Negative numbers (
[-2, -1, 0, 1]): returns 4; the checkx - 1 not in sworks across zero. - No two consecutive (
[0, 2, 4]): every number starts a run of length 1, so the answer is 1.
Common mistakes
- Starting a count from every number instead of only from run starts, which is O(n²) on one long run.
- Looping
for x in numsinstead offor x in s. The answer stays right, but a run start repeated many times is counted again each time: n/2 copies of 1 followed by 2 to n/2 is O(n²). - Sorting and forgetting to skip equal neighbours, so
[1, 2, 2, 3]looks like two runs of length 2.
Find the longest run where each value is exactly d more than the previous one, using values from the list. For [1, 3, 5, 9, 7, 2] with d = 2 the answer is 5 (1, 3, 5, 7, 9). Describe your approach, then write it if you like.
Compare with our answer
Same set, same rule for where a run starts, with 1 replaced by d. x starts a run when x − d is missing, and the run continues while x + d · length is present.
def longest_step(nums, d):
s = set(nums)
best = 0
for x in s:
if x - d not in s: # x starts a run
length = 1
while x + d * length in s:
length += 1
best = max(best, length)
return best
With d = 1 it is the original problem. Each value still belongs to exactly one run, so time stays O(n) and space O(n).
A strong answer mentions: the start-of-run test with x − d, why each value is still visited once, and that d = 1 gives back the original.
1. You are given the booked room numbers of a hotel, unsorted and possibly repeated, and must find the longest block of neighbouring rooms that are all booked, in O(n). Which approach fits best?
It is the same problem. The set plus run-start check is O(n). Sorting and a heap both cost O(n log n), and a boolean list needs memory proportional to the largest room number, not to n.
2. Why is the shown code O(n) even though it has a while loop inside a for loop?
Only numbers with no left neighbour start a count, and each number lies in exactly one run, so all the while steps together total at most the number of distinct values. Fast lookups alone are not enough: counting from every number would still be O(n²).
3. A learner writes for x in nums: instead of for x in s:. Which input now makes the code noticeably slow?
Every copy of 1 is a run start and walks the whole run again, about n²/4 steps in total. In the other lists each value appears once, so each run start is counted once and the time stays linear.
Score 60% or more and the lesson is marked complete.