Find the longest run of consecutive numbers in an unsorted list. Put them in a set, and only count up from numbers with no left neighbour.
▼The problem
LeetCode 128 (Medium). Given an unsorted array of integers, return the length of the longest run of consecutive values, in O(n) time.
Examples (LeetCode's): [100, 4, 200, 1, 3, 2] → 4 (1, 2, 3, 4) and [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] → 9 (0 to 8; the second 0 is a duplicate).
The solution
def longestConsecutive(nums):
seen = set(nums)
best = 0
for x in seen:
if x - 1 not in seen: # first domino
y = x
while y + 1 in seen: # push the next
y += 1
best = max(best, y - x + 1)
return bestTranscript
Longest Consecutive Sequence. Given an unsorted array of integers, return the length of the longest run of consecutive values, like five, six, seven. And do it in linear time.
Take one hundred, four, two hundred, one, three and two. One through four form a run, so the answer is four. The second example, zero through eight, gives nine.
The naive way sorts the numbers, then scans for runs. That works, but sorting costs order n log n time, not linear.
Instead, put every number in a hash set, so checking for a value takes constant time. Think of dominoes: a number starts a run only if the number just below it is missing. Only there do we count, checking x plus one, x plus two, and so on, while they're in the set.
In code, build the set and loop over it. If x minus one is missing, walk y upward while y plus one is present, then keep the longest length.
Try the first example. One hundred has no ninety nine, so it starts a run of one. Four has a three below it, so skip it. Two hundred is a run of one. One has no zero, so it pushes two, three and four: a run of four. Three and two are skipped. The answer is four.
Each number is checked once as a start, and walked over at most once inside a run, so it's order n time, and the set takes order n space.
Hash it, start at the bottom of each run, then walk up. That's Longest Consecutive Sequence.