Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input:nums = [100,4,200,1,3,2]
Output:4
The longest consecutive sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input:nums = [0,3,7,2,5,8,4,6,0,1]
Output:9
The longest consecutive sequence is [0,1,2,3,4,5,6,7,8]. Length is 9.
Constraints:
0 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
Hints
Hint 1Sorting is O(n log n) — the problem requires O(n). What structure gives O(1) membership?▼
If you sort the array first, you can scan linearly for sequences — but that's O(n log n). To hit O(n), you need a structure that answers "does n+1 exist?" in O(1). A Hash Set is the answer.
Hint 2Avoid counting the same sequence multiple times.▼
If you start counting from every number, you'll re-count sequences repeatedly. The fix: only start counting from a sequence's root — a number n where n - 1 is NOT in the set. This guarantees each sequence is only counted once.
Hint 3Each element is visited at most twice — still O(n) total.▼
When you find a root, run a while loop counting up (n, n+1, n+2, ...) until the next number isn't in the set. Even though this looks like a nested loop, each element can only be the subject of counting once across the entire iteration. Total operations ≤ 2n → O(n).
Brute Force Approach
O(n log n) Time
🔄
Sort Then Scan
Time O(n log n)Space O(1)
Sort the array, then scan linearly — consecutive equal or consecutive-by-1 elements extend the current sequence. Simple but violates the O(n) requirement.
1Sort nums — O(n log n).
2Track currentStreak and longestStreak.
3For each element: if it equals previous + 1, extend streak. If equal to previous (duplicate), skip. Otherwise reset streak to 1.
deflongestConsecutive(nums):
if not nums: return0nums.sort()
cur, best = 1, 1for i inrange(1, len(nums)):
if nums[i] == nums[i-1] + 1: cur += 1elif nums[i] != nums[i-1]: cur = 1
best = max(best, cur)
return best
Optimal Approach — HashSet Start Check
O(n) Time
🔍
Identifying Sequence Roots
Time O(n)Space O(n)
To achieve O(n), dump all array elements into a Hash Set for O(1) lookups. The trick to avoid re-checking identical sub-sequences is determining the start of a sequence. A number n is the start of a sequence only ifn - 1 does not exist in the Hash Set.
1Initialize a HashSet from nums.
2Iterate through each number n in the array.
3If n - 1 is absent from the set, n is a root. Count up: n+1, n+2, ... until the sequence ends.
4Update the running longest sequence tracker.
READYPress ▶ or step forward to begin.
✓
—
Executing Code
deflongestConsecutive(nums):
numSet, longest = set(nums), 0
for n in nums:
if (n - 1) not in numSet:
length = 0
while (n + length) in numSet:
length += 1
longest = max(longest, length)
return longest
Time Complexity Analysis
Build hash setO(n)One pass over nums to insert all elements into the set. Each insert is O(1) average.
Outer loopO(n)Iterates over every element in nums once. For most elements, the n-1 ∈ set check is true and we skip immediately — O(1) per element.
Inner while loopO(n) totalOnly runs from sequence roots. Crucially, each element can only be counted once across all while-loop iterations combined. No element is ever re-counted — so the total work across all inner loops is at most n iterations.
TotalO(n)The apparent O(n²) nested loop structure is actually O(n) amortized — the inner loop's total iterations across the entire algorithm is bounded by n, not n per outer iteration.
Amortized O(n) explained: Think of it as a bank account. We have n tokens, one per element. Each token is spent exactly once by the while loop when that element gets counted in its sequence. Once spent, it is never counted again (because future outer-loop iterations skip non-roots). Total tokens spent ≤ n → O(n) total.
Discussion
…