Longest Consecutive Run
Problem
Given an unsorted list of integers, find the length of the longest group of numbers that could be lined up as consecutive values with no gaps. The numbers do not have to be adjacent in the list, and duplicates count only once. Aim for a solution that does not sort the input.
Examples
Input: nums = [9, 4, 2, 3, 1, 8]
Output: 4
Why: 1, 2, 3 and 4 form an unbroken chainInput: nums = [5, 5, 5]
Output: 1
Why: duplicates add nothing, the chain is just the value 5Input: nums = []
Output: 0
Why: edge case, there is no chain to measureHints
0 / 3
Sorting solves it in n log n. To beat that, think about answering the question is the next number present without scanning the list again.
Membership testing over a set of the values makes any single step of a chain a constant-time question. The remaining problem is not walking the same chain many times.
Put every value into a set. Only start counting from a value whose predecessor is missing, since that is the head of its chain. From each head, keep stepping upward while the next value is present, and track the longest chain measured.
Solution
Loading the values into a set turns each chain step into a constant-time membership test, and dropping duplicates for free. Counting starts only at values whose predecessor is absent, which means each chain is walked exactly once from its head rather than once per member. That guard is what keeps the nested loop linear overall. Time is O(n) on average, and space is O(n) for the set.
def longest_consecutive_run(nums):
pool = set(nums) # duplicates collapse, lookups are cheap
best = 0
for x in pool:
if x - 1 in pool: # only count starting from a chain head
continue
length = 1
while x + length in pool: # walk the chain upward
length += 1
best = max(best, length)
return best
print(longest_consecutive_run([9, 4, 2, 3, 1, 8])) # -> 4
print(longest_consecutive_run([5, 5, 5])) # -> 1
print(longest_consecutive_run([])) # -> 0Stuck on the idea rather than the code? Hash Table Basics covers it.