Longest Consecutive Sequence
MediumArrays & Hashing · Airbnb
Given an unsorted integer array nums, return the length of the longest run of consecutive integers that can be formed from its values, where each value in the run is exactly 1 larger than the previous one.
The values may appear anywhere in nums, in any order. A value that appears several times still counts only once. Return 0 for an empty array.
Your algorithm must run in O(n) time.
Example 1
- Input:
- nums = [12,3,10,2,11,5,1,13,4]
- Output:
- 5
- Explanation
- 1, 2, 3, 4, 5 are all present, a run of 5. 10 through 13 is another run, but only of length 4.
Example 2
- Input:
- nums = [7,7,8,9,20]
- Output:
- 3
- Explanation
- 7, 8, 9 is the longest run. The second 7 does not make it longer.
Example 3
- Input:
- nums = []
- Output:
- 0
- Explanation
- There are no values, so there is no run at all.
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9