Longest Consecutive Sequence
Given an unsorted array, return the length of the longest run of consecutive integers (in O(n) time).
- 0 <= nums.length <= 10⁵
- -10⁹ <= nums[i] <= 10⁹
Intuition
Longest consecutive sequence finds the longest run of consecutive integers present in an unsorted array, in O(n) time. That requirement is what makes the problem interesting — sorting gives the answer in O(n log n) and is explicitly not good enough.
Without sorting, membership must be tested some other way, and a hash set provides it in O(1). But scanning outward from every element still costs O(n²) in the worst case, since each element of a long run re-walks the same sequence.
The fix is a single check that eliminates all the redundant work:
- Only start counting from an element that begins a sequence — one where num − 1 is absent from the set.
Every run is then walked exactly once, from its smallest member. An element in the middle of a run is skipped immediately at O(1) cost, so the total work across all elements is linear despite the inner loop.
Omitting that check is what makes the naive version quadratic, and it is the entire difference between an accepted and a timed-out solution.
From a genuine start, count upward while num + 1 remains in the set, tracking the longest run found.
Using a set rather than a list for membership is equally essential — in on a list is O(n) and silently restores the quadratic behaviour even with the start check in place.
Duplicates are handled automatically, since a set collapses them and they cannot lengthen a consecutive run.
An empty array returns 0, which falls out naturally when no iterations occur.
A hash set turns "is n+1 present?" into O(1), but the real insight is the n - 1 not in s guard: it starts a walk only from a sequence's first element. That single check is what keeps the total work linear despite the inner while loop — every element is walked over at most once across the whole run.
Approach
Before reading on: sorting gives O(n log n) and the target is O(n). Put every value in a set, then ask what test would stop you from walking the same run five times over. That one guard is the whole solution.
Rule out sorting
Sorting answers the question in O(n log n), but the problem demands O(n) — so membership must be tested without ordering the data.
Load everything into a set
A hash set gives O(1) membership tests. Using a list instead silently restores quadratic behaviour, since in on a list is O(n).
Only start from a sequence's beginning
Count outward only when num - 1 is absent from the set. This single check is what makes the algorithm linear rather than quadratic.
Count upward from there
While num + 1 is present, extend the run. Each sequence is walked exactly once, from its smallest member.
Skip interior elements cheaply
An element mid-run fails the start check and is discarded in O(1). This is why the inner loop does not compound the cost.
Track the longest run
Keep the maximum length seen. An empty array yields 0 naturally, since no iterations occur, and duplicates collapse in the set.
Cost of the approach
Each element is visited a constant number of times overall, giving O(n) time and O(n) space for the set.
Solution & live demo
Common pitfalls
Walking from every element
for n in s:
length = 1
while n + length in s:
length += 1for n in s:
if n - 1 not in s:
length = 1
while n + length in s:
length += 1Without the guard, a run of length k is re-walked from each of its k members, giving O(n²) on a single long sequence. Starting only where a run begins means each element is visited once by exactly one walk.
Sorting first
nums.sort() # then scan for runs
s = set(nums)
Sorting is correct but O(n log n), and the problem asks for O(n). The set gives constant-time membership, which is the only ordering information the algorithm actually needs.
Iterating the list instead of the set
for n in nums:
for n in s:
Duplicates in the input cause the same run to be walked repeatedly, reintroducing the quadratic blowup the guard was meant to prevent. Iterating the set visits each distinct value once.
Edge cases
The set collapses duplicates, so a repeated value neither lengthens nor restarts a run.
The loop never runs; best stays 0.
Each lone number is its own run of length 1 because its neighbor is absent.