Problem 5 · Arrays & Hashing

Longest Consecutive Sequence

MediumClassic DSA & systems

01Problem

Given an unsorted integer array, return the length of the longest run of consecutive integers, in O(n) time.

02Key insight

Put everything in a set and only start counting from run starts (x-1 not in set), so each element is visited a constant number of times overall.

03Solution

solution.pypython11 lines

def longest_consecutive(nums: list[int]) -> int:
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 in values:
            continue  # not the start of a run
        length = 1
        while x + length in values:
            length += 1
        best = max(best, length)
    return best

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 3 passing

tests.pypython3 lines

assert longest_consecutive([100,4,200,1,3,2]) == 4
assert longest_consecutive([0,3,7,2,5,8,4,6,0,1]) == 9
assert longest_consecutive([]) == 0

04Staff-level follow-up

What if numbers arrive as a stream? Use union-find (or a map of run boundaries) to merge x with x-1 and x+1 on insert, tracking max component size in near-O(1) amortised.