Longest consecutive run
We'll cover the following
Find the length of the longest run of consecutive numbers (like 4, 5, 6, 7) in an unsorted array.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
x90
81
182
163
124
105
136
77
28
69
1910
2111
1112
2213
2014
1515
8 exists, so 9 is not the start of a run. Skip it.
best 0
1 / 17
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(n) | Only run starts walk forward, so each number is visited at most twice. |
In Python
def longest_consecutive(nums):
s, best = set(nums), 0
for x in s:
if x - 1 not in s: # x starts a run
y = x
while y in s: y += 1
best = max(best, y - x)
return bestSummary: say it in the interview
- Put everything in a set. Only start counting from a number whose predecessor is missing, then walk up. Each number is walked once, so it stays linear.
- Time O(n), space O(n). Only run starts walk forward, so each number is visited at most twice.