You are given an unsorted list of integers nums. Return the length of the longest run of
consecutive integers (such as 4, 5, 6, 7) whose values all appear somewhere in nums. The values
can sit at any positions, and a value that appears more than once counts once.
Aim for O(n) time, which rules out sorting.
Example 1
- Input
- nums = [10, 4, 20, 1, 3, 2]
- Output
- 4
Example 2
- Input
- nums = [5, 6, 6, 100, 7, -1, 0]
- Output
- 3
Constraints
numsholds 0 to 10⁵ numbers.- Every number is between −10⁹ and 10⁹.
Show the pattern
Hashing
Asking "is x + 1 here?" again and again is a membership test, and a hash set answers it in constant time, so you can grow each run from its first value without sorting.
See hashing in a visualiserShow the approach
Put all the values in a hash set, which also drops repeats. For each value x in the set, skip
it unless x − 1 is missing: only then is x the first value of a run. From a first value, step
up through x + 1, x + 2, … while each is in the set, and keep the longest length seen.
Each value is looked at once as a possible start, and at most once while a run is counted, so the whole thing is O(n).
Time: O(n) · Space: O(n)