Longest Consecutive Sequence
Find the length of the longest run of consecutive whole numbers hidden in an unsorted array.
- Find the start of a sequence
- Hash set membership
Before this, know: Hash sets (Set in JavaScript, set in Python), While loops
You get an unsorted array of whole numbers, nums. A consecutive
sequence is a run of numbers that each go up by exactly 1, like 1, 2, 3, 4. The
numbers can be anywhere in the array, in any order. Return the length of the
longest such run.
Example: nums = [100, 4, 200, 1, 3, 2].
- 1000
- 41
- 2002
- 13
- 34
- 25
- 1
- 2
- 3
- 4
- 100
- 200
The rules that matter:
- Only the values matter, not where they sit in the array.
- Duplicates don’t extend a run:
[1, 2, 2, 3]has a longest run of 3 (1, 2, 3). - An empty array has answer 0. Numbers can be negative.
- The problem demands O(n) time, which rules out sorting (O(n log n)). (Big-O notation is a short way of saying how the work grows as the input grows: O(n) means “double the array, double the work”, and sorting grows a bit faster than that. See Big-O in 5 minutes.)
So two questions matter for each number x:
- Is
xthe start of a run? That’s true exactly whenx − 1is not in the array. - If it is, how long is the run? Keep asking “is
x + 1here?x + 2?” until the answer is no.
Both are “is this value here?” questions, which a hash set answers in about
one step. (A hash set is a collection that remembers values and can say whether
a value is in it almost instantly; Set in JavaScript, set in Python.)
Pause and think
The starts are 1 (0 isn’t there), 100 (99 isn’t there) and 200 (199 isn’t there). The numbers 2, 3 and 4 are not starts, because 1, 2 and 3 are present. So we only count from 1, 100 and 200: lengths 4, 1 and 1.
From every number, count upward: is num + 1 in the array? num + 2? Each
question scans the whole array (includes in JS, in on a list in Python).
Brute force: count up from every number
nums = [100, 4, 200, 1, 3, 2]
- 1000
- 41
- 2002
- 13
- 34
- 25
- looking for
- 101
- length
- 1
- best
- 0
- cells read
- 6
- Starting number
- Found by the scan
From 100: scan the whole array for 101. Not there, so this streak has length 1. (6 cells read so far.)
Which line is running?
function longestConsecutive(nums) { let best = 0; for (const num of nums) { let length = 1;Running now: while (nums.includes(num + length)) { // scans the whole array length++; } best = Math.max(best, length); } return best;}Brute force: count up from every number
function longestConsecutive(nums) { let best = 0; for (const num of nums) { let length = 1; while (nums.includes(num + length)) { // scans the whole array length++; } best = Math.max(best, length); } return best;}def longest_consecutive(nums): best = 0 for num in nums: length = 1 while num + length in nums: # scans the whole list length += 1 best = max(best, length) return bestTwo kinds of waste pile up:
- Every search scans the array. “Is 5 in the array?” reads up to n cells.
- We recount the same runs. For the run 1, 2, 3, 4 we count from 1 (4 long), then from 2 (3 long), from 3, and from 4. That’s 4 + 3 + 2 + 1 = 10 searches for one run.
If the whole array is one long run of n numbers, we do about n × n ÷ 2 searches, each reading up to n cells: O(n³). For 1,000 numbers that’s hundreds of millions of reads.
Sort the numbers, then walk through them: if a number is exactly 1 more than the previous one, the run grows; if it’s equal, skip it (duplicate); otherwise the run restarts at 1.
Sort, then walk
function longestConsecutive(nums) { if (nums.length === 0) return 0; const s = [...nums].sort((a, b) => a - b); let best = 1; let length = 1; for (let i = 1; i < s.length; i++) { if (s[i] === s[i - 1]) continue; // duplicate: streak unchanged length = s[i] === s[i - 1] + 1 ? length + 1 : 1; best = Math.max(best, length); } return best;}def longest_consecutive(nums): if not nums: return 0 s = sorted(nums) best = length = 1 for i in range(1, len(s)): if s[i] == s[i - 1]: continue # duplicate: streak unchanged length = length + 1 if s[i] == s[i - 1] + 1 else 1 best = max(best, length) return bestThat’s O(n log n), a perfectly good answer in practice. But the problem asks for O(n), so we need to drop the sort.
Fix the first waste with a hash set (each search becomes one step). Fix the second waste with one extra question.
Pattern
Find the start of a sequence
Use it when: you need runs or chains of related values (x, x + 1, x + 2…) in unsorted data, in O(n).
Signal words
- “consecutive”
- “longest sequence”
- “unsorted”
- “O(n) time”
- “chain of”
- Put all the numbers in a hash set. Duplicates disappear.
- Set
best = 0. - For each number
numin the set: ifnum − 1is in the set, skip it. It’s in the middle of a run. - Otherwise
numstarts a run. Setlength = 1, and whilenum + lengthis in the set, add 1 tolength. - Update
bestwith the bigger ofbestandlength. - Return
best.
Press Play. The top row is the set in the order the loop visits it; the number line below shows the values in order with gaps marked “…”. Watch the non-starts fade out after a single lookup, and watch each start sweep along its run. Keep an eye on the lookups counter.
Hash set, count only from starts
nums = [100, 4, 200, 1, 3, 2]
- 1000
- 41
- 2002
- 13
- 34
- 25
- 1
- 2
- 3
- 4
- 100
- 200
- length
- —
- best
- 0
- lookups
- 0for 6 numbers
- Number we're looking at
- Not a start (skipped)
- Streak being counted
- Lookup found
- Lookup not found
- Longest streak
Put every number into a hash set: 6 distinct numbers. Now "is x in the set?" takes about one step. The number line below shows them in order, with … where numbers are missing.
Which line is running?
function longestConsecutive(nums) {Running now: const set = new Set(nums); // instant "is x here?" and no duplicates let best = 0; for (const num of set) { if (set.has(num - 1)) continue; // not a start: num - 1 will count it let length = 1; while (set.has(num + length)) { length++; } best = Math.max(best, length); } return best;}A while inside a for usually means O(n²). Here it doesn’t, and this is the
question interviewers love. Count the work per number instead of per loop:
- Every number gets one “is
num − 1here?” lookup in theforloop. That’s n lookups. - The
whileloop only runs from a start, and it walks forward through that start’s own run. Runs don’t overlap, so every number is stepped on by thewhileloop at most once in total, plus one failed lookup at the end of each run.
So the total is at most about n + n + n = 3n lookups: O(n). In “Example 2” there are 9 distinct numbers and the counter ends at 18. Without the start check, the run 0…8 would be counted from 0, then from 1, then from 2…: 9 + 8 + … + 1 = 45 steps instead.
Hash set, count only from starts
function longestConsecutive(nums) { const set = new Set(nums); // instant "is x here?" and no duplicates let best = 0; for (const num of set) { if (set.has(num - 1)) continue; // not a start: num - 1 will count it let length = 1; while (set.has(num + length)) { length++; } best = Math.max(best, length); } return best;}def longest_consecutive(nums): num_set = set(nums) # instant "is x here?" and no duplicates best = 0 for num in num_set: if num - 1 in num_set: continue # not a start: num - 1 will count it length = 1 while num + length in num_set: length += 1 best = max(best, length) return bestPython puts the “skip” check on two lines (5–6), so from there on its line numbers run one ahead of JavaScript’s.
- Line 1: define the function. (LeetCode:
var longestConsecutive = function(nums)in JS,def longestConsecutive(self, nums)inclass Solutionin Python.) - Line 2: build the set from the whole array in one go.
new Set(nums)/set(nums). Duplicates disappear, which is exactly what we want. - Line 3:
beststarts at 0, the right answer for an empty array. - Line 4: loop over the set, not over
nums. Ifnumscontained the same start many times (like 100,000 copies of 1), looping overnumswould recount that run every time. - Line 5 (JS) / lines 5–6 (Python): if
num − 1is present,numis in the middle of a run;continueskips to the next number. - Line 6 (JS) / line 7 (Python):
numis a start, so the run so far is 1 long. - Lines 7–8 (JS) / lines 8–9 (Python): keep asking about the next number
up,
num + length, and grow the run while the answer is yes. - Line 10 (both): keep the longest run seen.
- Line 12 (JS) / line 11 (Python): return it.
One small difference: JavaScript visits a Set in the order values were added;
Python visits a set in its own internal order. The order changes which start
we meet first, but never the answer.
| num | num − 1 in set? | start? | counting | length | best |
|---|---|---|---|---|---|
| 100 | 99: no | yes | 101? no | 1 | 1 |
| 4 | 3: yes | no, skip | 1 | ||
| 200 | 199: no | yes | 201? no | 1 | 1 |
| 1 | 0: no | yes | 2? yes, 3? yes, 4? yes, 5? no | 4 | 4 |
| 3 | 2: yes | no, skip | 4 | ||
| 2 | 1: yes | no, skip | 4 |
The num = 1 row does all the real work: starting at 1, it walks the whole run 1–4. The rows for 4, 3 and 2 each cost a single lookup, because those numbers are already covered by that run.
Brute force
Time
O(n³)
Up to n × n ÷ 2 searches (recounting runs from every number), each scanning up to n cells.
Space
O(1)
Only a few counters.
Sort, then walk
Time
O(n log n)
Sorting dominates; the walk afterwards is n steps.
Space
O(n)
The sorted copy.
Hash set, count only from starts
Time
O(n)
Each number gets one start check and is stepped on by at most one while loop, so at most about 3n lookups.
Space
O(n)
The set holds every distinct number.
What to say out loud, in this order:
- “Sorting gives O(n log n). The problem wants O(n), so I’ll use a hash set for O(1) lookups.”
- “To avoid recounting, I only count from numbers whose predecessor is missing: the starts of runs.”
- “It’s O(n) even with the inner while: each number is visited at most once by any while loop.”
- Trace a small example, pointing out the skipped non-starts.
Likely follow-up questions:
- “Return the sequence itself, not just its length?” Remember the start of the best run; the run is start, start + 1, …
- “Why not a hash map?” We only need “is it here?”, not a value per key, so a set is enough.
- “Could Union-Find solve this?” Yes, by joining each x with x + 1, but the set solution is simpler and just as fast.
Related problems:
- Contains Duplicate (this week): the simplest use of a hash set’s instant lookup.
- Two Sum (this week): asks the set-style question “is my partner here?” for a different partner (target − x instead of x + 1).
- Top K Frequent Elements (this week): another problem where the follow-up asks you to beat O(n log n) without sorting.