Coding Interview PatternsLongest Consecutive Sequence
MediumHash Maps
Longest Consecutive Sequence
Explanation & Solution
Description
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.
Input:nums = [100,4,200,1,3,2]
0
100
1
4
2
200
3
1
4
3
5
2
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
Approach
Hash Maps pattern
1. Build a Hash Set
- Insert all numbers from
numsinto aSet - This gives us O(1) lookups and automatically removes duplicates
2. Identify Sequence Starts
- For each number
numin the set, check ifnum - 1exists in the set - If
num - 1does not exist, thennumis the start of a consecutive sequence - This check ensures we only begin counting from the smallest number in each sequence
3. Extend the Sequence
- Starting from the sequence start, keep checking if the next consecutive number (
current + 1) exists in the set - Increment the streak counter for each consecutive number found
- Continue until the chain breaks
4. Track the Maximum
- After each sequence is fully counted, update
longestwith the maximum of the current streak and the previous longest - After iterating through all numbers, return
longest
Key Insight
- The key trick is only starting a count from sequence beginnings (numbers with no predecessor in the set). This prevents redundant counting and ensures each number is visited at most twice — once in the outer loop and at most once while extending a sequence
- Sorting would solve this in O(n log n), but the hash set approach achieves the required O(n) time
Time
O(n)each number is processed at most twiceSpace
O(n)the set stores all unique numbersVisualization
Input:
[100, 4, 200, 1, 3, 2]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps