Appearance
4.4.9 — Longest Consecutive Sequence
LeetCode 128 · Medium · ★ Blind 75
The problem
You are given an unsorted list of whole numbers called nums. Find the length of the longest run of consecutive numbers that are all present in the list. Consecutive numbers are numbers that go up by exactly 1 each time, like 4, 5, 6, 7. They do not have to sit next to each other in the list. They only have to be present somewhere.
nums = [100, 4, 200, 1, 3, 2] → 4 (the run 1, 2, 3, 4)
nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] → 9 (the run 0 to 8)
nums = [] → 0The list has up to 100,000 numbers, each between minus one billion and one billion. The problem requires an O(n) solution. That rule is the real difficulty.
What the problem is really asking
If you sorted the list in your head, the runs would be easy to see. In [100, 4, 200, 1, 3, 2] sorted, you get 1, 2, 3, 4, 100, 200, and the run 1 to 4 jumps out.
But the problem forbids the time that sorting costs. So we must find the runs while only asking one kind of question: "is this number in the list?" For example, starting from 1, we ask "is 2 in the list? is 3? is 4? is 5?" and stop at the first "no".
A question of the form "is this in the list?" is a job for a hash set, which answers it in constant time.
The brute force, and where it wastes work
Sort, then count runs. This is a perfectly good first answer to say out loud.
python
def longestConsecutive(nums):
if not nums:
return 0
nums = sorted(set(nums)) # remove repeats, then sort
best = length = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1] + 1: # continues the run
length += 1
best = max(best, length)
else: # the run is broken
length = 1
return bestset(nums) removes repeated numbers first. Without that, [1, 1, 2] would need a third case for "equal neighbours".
Sorting takes O(n \log n) time, which the problem rules out.
The waste in one sentence: sorting works out the exact order of every number, but we only need to know which numbers exist and whether the next number up exists.
The idea
Put every number into a set. Now "is n + 1 present?" costs constant time, and from any number we can walk forward along its run.
But if we walk from every number, we repeat work. In [1, 2, 3, 4] we would walk from 1 (4 steps), then from 2 (3 steps), then from 3 (2 steps), then from 4 (1 step). Every run gets walked again from each of its members. That is O(n^2) again.
The fix is one rule, and it is the whole algorithm:
Only start walking from a number that begins a run. A number
nbegins a run exactly whenn - 1is not in the set.
If n - 1 is in the set, then n sits in the middle of a run. That run will be walked from its true start anyway, so we skip n.
Think of tracing rivers on a map. If you dropped a boat in at every point along a river, you would trace the same water to the sea again and again. Instead, you only drop a boat at each river's source. A number is a "source" only if the number one below it is missing.
The solution
python
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
s = set(nums) # (1)
best = 0 # (2)
for n in s: # (3)
if n - 1 in s: # (4)
continue
length = 1 # (5)
while n + length in s: # (6)
length += 1
best = max(best, length) # (7)
return bestts
function longestConsecutive(nums: number[]): number {
const s = new Set(nums); // (1)
let best = 0; // (2)
for (const n of s) { // (3)
if (s.has(n - 1)) continue; // (4)
let length = 1; // (5)
while (s.has(n + length)) length++; // (6)
best = Math.max(best, length); // (7)
}
return best;
}Line by line
(1) s = set(nums). Put every number into a set. This does two jobs. It lets us ask "is this number present?" in constant time. And it removes repeats, so [1, 1, 2] correctly gives 2, not 3.
(2) best = 0. The longest run found so far. Starting at 0 means an empty list returns 0 without any special case.
(3) for n in s. Loop over the set, not the original list. If the list held the same number many times, looping over the list would visit it many times. The answer would still be right, but we would repeat the check in line (4) for every copy, and the speed argument below would no longer hold.
(4) The run-start check. If n - 1 is in the set, n is not the start of its run. We skip it with continue, which jumps straight to the next turn of the loop. This one line is what makes the solution fast.
(5) length = 1. We got past line (4), so n starts a run. The run contains at least n itself, so its length is at least 1.
(6) Walk forward. Is n + 1 present? If so, the length becomes 2. Then we check n + 2, and so on. We use n + length because, when the run so far has length numbers, the next number we need is exactly length steps above n. The loop stops at the first missing number.
(7) Keep the best. max(best, length) keeps whichever is larger: the best run found earlier, or this one.
Trace
Take nums = [100, 4, 200, 1, 3, 2]. The set is {1, 2, 3, 4, 100, 200}. A set has no fixed order, so the order below is just one possibility. The answer is the same in any order.
n | Is n − 1 present? | What happens | Steps in the inner loop | best after |
|---|---|---|---|---|
| 1 | no (0 missing) | walk: 2 ✓, 3 ✓, 4 ✓, 5 ✗ → length 4 | 4 | 4 |
| 2 | yes | skip | 0 | 4 |
| 3 | yes | skip | 0 | 4 |
| 4 | yes | skip | 0 | 4 |
| 100 | no | walk: 101 ✗ → length 1 | 1 | 4 |
| 200 | no | walk: 201 ✗ → length 1 | 1 | 4 |
The answer is 4. Count the inner-loop steps: 4 + 1 + 1 = 6. There are 6 distinct numbers. That is not a coincidence, as the next section shows.
Complexity, derived: why this is not O(n^2)
This is the reason the problem is asked. There is a while loop inside a for loop, and a loop inside a loop usually means n \times n work. Here it does not, and you must be able to explain why.
The mistake is to imagine the inner loop running for a long time on every turn of the outer loop. It cannot. Instead of counting the work per turn, count the total work over the whole program.
- The inner loop only runs when
nstarts a run, because of line (4). - When it runs, it walks that one run from start to end, once.
- Every number belongs to exactly one run. Two runs that shared a number would join up into one run.
- So every number is stepped over by the inner loop at most once in the whole program.
That means the total work of the inner loop, added up over every turn, is at most the number of distinct values, which is at most n. The outer loop does a constant amount of work for each of at most n values. Building the set in line (1) touches each of the n numbers once.
So the total time is O(n) + O(n) + O(n) = O(n). The set holds up to n numbers, so the space is O(n).
This way of counting has a name: amortized analysis. "Amortized" means spreading a cost out. You charge each unit of work to one particular element, and then show that no element is ever charged twice. You will use the exact same argument three more times in this Part.
- The sliding window in 4.6, where the left edge of the window only ever moves right.
- The monotonic stack in 4.8, where each item is pushed once and popped at most once.
- Manacher's algorithm in 4.31, where a centre point never moves backwards.
The mistake that quietly costs you the linear time
Delete line (4), and the code still returns the right answer. It just becomes O(n^2), because every run is walked again from each of its members.
No error appears, and every small example passes. Only the largest test times out. That is the dangerous kind of bug, because it looks like success until the input gets big.
Edge cases
- An empty list. The loop never runs, and
beststays 0. - All numbers the same, such as
[7, 7, 7]. The set is{7}, the run is just 7, and the answer is 1. - Negative numbers and zero, such as
[-1, 0, 1]. The set does arithmetic on numbers and does not care about their sign. The run starts at −1 because −2 is missing, and the answer is 3. - Huge gaps, such as
[-1000000000, 1000000000]. Two runs of length 1.
The range of minus one billion to one billion matters in one way. It rules out a plain list of true/false flags indexed by value. That list would need two billion slots to hold at most a hundred thousand numbers. A set is the only sensible choice.
Variations you will meet
- Union-find. Treat each number as a point, and join
nton + 1whenever both exist. The answer is the size of the biggest joined group. It is more code here, but it shines when numbers arrive one at a time and you must answer between arrivals. 4.19.2 builds it. - Longest Consecutive Sequence in a Binary Tree. Same words, but a different problem. The run must follow parent-to-child links in a tree, so it is a tree walk, not a set problem. Do not mix them up.
- Longest Harmonious Subsequence. Find the most numbers you can pick so that the biggest and smallest differ by exactly 1. Count each value, then for each value
n, add its count to the count ofn + 1. A single lookup per value, no walking.
The general lesson has two levels. The narrow one is: use a set to ask "is this present?", and walk each group only from its agreed starting point. The wider one is: do the work for each group only once, from one chosen member. The same guard appears as "only start a flood fill from a cell you have not visited yet" in 4.20.
What the interviewer will push on
"There is a loop inside a loop. Why is it not O(n^2)?" This gets asked here more than anywhere else in the group, because the code looks quadratic. Give the four-step argument above.
"Why check n - 1 and not n + 1?" You need one agreed starting point per run. The smallest number is a natural choice. Checking n + 1 instead finds the end of each run, and that also works if you then walk downwards.
"What if you had to return the run itself, not just its length?" Remember the starting number of the best run along with its length. The run is that number up to that number plus the length minus one.
"What if the numbers arrive one at a time?" The set solution needs the whole list first. Union-find handles arrivals, by joining each new number with its neighbours and keeping a running maximum.
One thing to volunteer: give the proof that the solution is linear before they ask. Explaining why your own speed claim is true is one of the clearest signals of real understanding.
Next: 4.5 Two Pointers. We drop the hash map and remove the nested loop a different way: two positions moving through one list, under a rule that proves neither ever needs to go back.