Learning Outcome
After this lesson, you should be able to use a hash set to detect sequence starts and avoid repeated expansion.
Problem Statement
Given an unsorted integer array, return the length of the longest consecutive sequence.
| Input | Output | Why |
|---|---|---|
nums = [100,4,200,1,3,2] | 4 | The longest consecutive run is 1,2,3,4. |
Brute Force Approach
Sort the array and scan consecutive groups. This works, but sorting costs extra time.
Optimized Approach
Put every number in a set. Only start expanding from x when x
- 1 is absent, because that means x is the beginning of a sequence.
Exact Pseudocode
seen = set(nums)
best = 0
for x in seen:
if x - 1 is not in seen:
length = 1
while x + length is in seen:
length += 1
best = max(best, length)
return bestReference Code
class Solution:
def longestConsecutive(self, nums):
seen = set(nums)
best = 0
for x in seen:
if x - 1 not in seen:
length = 1
while x + length in seen:
length += 1
best = max(best, length)
return bestSample Dry Run
| Step | State | Result |
|---|---|---|
| Build set | {100,4,200,1,3,2} | Lookups are O(1) average |
| x = 1 | 0 is absent | Start sequence |
| Expand | 2,3,4 exist | length = 4 |
| Other numbers | 2,3,4 are skipped as starts | answer = 4 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | Each number is inserted once and expanded only from true sequence starts. |
| Space | O(n) | The hash set stores unique numbers. |
Edge Cases
- Duplicates should not extend a sequence twice.
- An empty array returns 0.
- Negative numbers work the same as positive numbers.
Interview Checklist
Check x
- 1 before expanding.
- Iterate over the set, not necessarily the original array.
- Do not sort if the target is linear time.
FAQs
Why only expand from sequence starts?
If x
- 1 exists, then x belongs to a sequence that already starts earlier.
Why does this stay O(n)?
Every number is part of at most one successful expansion chain.
What is the core pattern?
Hash set lookup with sequence-start detection.