Mid-levelMid (3–6 yrs)CodingPythonGoogleAmazon

Longest Consecutive Sequence

Given an unsorted array of integers, return the length of the longest consecutive elements sequence. Aim for O(n) time.

Answers use simple, clear English.

Time: O(n)Space: O(n)

Quick interview answer

Put numbers in a set. Only start a streak when num-1 is absent. Count upward while num+1 exists.

Detailed answer

Put numbers in a set. Only start a streak when num-1 is absent. Count upward while num+1 exists. Each number is visited a constant number of times → O(n). Sorting is O(n log n) and acceptable if O(n) is not required.

Full explanation

Sorting is O(n log n) and acceptable if O(n) is not required.

Real example & use case

Loyalty program: longest streak of consecutive active days from sparse login timestamps.

Pros & cons

Pros: expected O(n). Cons: hash set memory; worst-case hash degradation rare in practice.

Code example

def longest_consecutive(nums: list[int]) -> int:
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 in s:
            continue
        length = 1
        while x + length in s:
            length += 1
        best = max(best, length)
    return best

Practice code · python (view only · no execution)

def longest_consecutive(nums: list[int]) -> int:
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 in s:
            continue
        length = 1
        while x + length in s:
            length += 1
        best = max(best, length)
    return best

#hashset#blind75