128. Longest Consecutive Sequence
Your function receives an unsorted integer array nums and returns the length of the longest run of consecutive values — the largest k such that some v, v+1, v+2, …, v+k−1 all appear somewhere in the array. The values only need to exist in the array; they do not have to sit next to each other, and duplicates count once.
An empty array has answer 0.
Sorting gives an easy O(n log n) answer — the interview follow-up is to do it in O(n) time.
Example 1:
Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The values 1, 2, 3, 4 all appear, forming a consecutive run of length 4. Neither 100 nor 200 extends any run.
Example 2:
Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Explanation: Every value from 0 through 8 appears (0 twice, which counts once), so the run 0…8 has length 9.
Constraints:
- 0 ≤ nums.length ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
- Duplicates may appear; each distinct value counts once toward a run.
Hints:
After sorting, consecutive values sit next to each other, so one linear scan counts runs — but that is O(n log n). What structure gives O(1) membership tests without sorting?
Dump everything into a hash set. For any value v you can ask 'is v+1 present?' in O(1) and walk a run upward.
Walking upward from every value is O(n²) on a long run. Only start walking when v−1 is absent — v is then the *start* of its run, so every element is visited a constant number of times.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [100, 4, 200, 1, 3, 2]
Expected output: 4