mediumHash maps and sets target 25 min
Longest consecutive sequence
You get a list of integers nums in no particular order. A consecutive run is a stretch of integers with no gaps, such as 4, 5, 6, 7. Return the length of the longest run whose numbers all appear somewhere in nums.
The numbers of a run do not need to sit next to each other in the list, and a value that appears more than once counts once. An empty list gives 0. Aim for O(n) time, faster than sorting.
Example 1
Input
nums = [8, 3, 50, 5, 4, 9]Output33, 4 and 5 are all present. 8 and 9 form a run of 2, and 50 a run of 1.
Example 2
Input
nums = [2, 1, 2, 0, -1]Output4The run is -1, 0, 1, 2. The second 2 adds nothing.
Example 3
Input
nums = []Output0No numbers, so no run.
Constraints
0 ≤ len(nums) ≤ 105
-109 ≤ nums[i] ≤ 109
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.