Description
Return the length of the longest run of consecutive integer values, regardless of their original positions.
Solution
def longest_consecutive(nums):
values = set(nums)
best = 0
for value in values:
if value - 1 not in values:
end = value
while end in values:
end += 1
best = max(best, end - value)
return bestExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[8,2,4,3,2]]- Output
3
The run 2, 3, 4 has length three; repeated 2 does not extend it.
Example 2
- Input
[[10]]- Output
1
A lone value is a run of length one.
Example 3
- Input
[[]]- Output
0
No values means no run.
Approach
Store distinct values and grow a run only from a value with no predecessor.
Time & space
O(n) expected time; O(n) space. Values are within the problem's signed integer bounds. Here n is the input length.