Longest Consecutive Sequence
The key idea
Drop every value into a hash set, then only start counting a run from a value
x whose predecessor x - 1 is not in the set. That value is the head of its run, so each run is walked exactly once and the whole scan stays O(n).Problem
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
A consecutive elements sequence is a run of numbers that follow one another with no gaps, such as [3, 4, 5, 6]. The numbers may appear in any order inside nums, and the run you measure does not have to be contiguous in the array — only the values must be consecutive.
You must write an algorithm that runs in O(n) time.
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
Examples
Input: nums = [100,4,200,1,3,2]
Output: 4
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest PalindromeEASY
- Majority Element IIMEDIUM