Longest Consecutive Sequence

Interview Prep

Warm-upArrays & Hashingarrayshashset

The problem

Given an unsorted array of integers, return the length of the longest sequence of consecutive integers (e.g., 5, 6, 7, 8) present in the array. Required time: O(n).

Why O(n) feels surprising

The obvious approach is to sort and count adjacent runs: O(n log n). The challenge ramps up because the problem demands O(n). The trick is so satisfying it's become a "favourite" interview question: drop the values in a hashset, then make sure you only start counting from sequence heads.

Pattern: head-only walking

A "sequence head" is a value x where x − 1 is not present in the set. Only those start a walk. From a head, walk forward in the set until the chain breaks. Across all heads, each value is visited at most twice (once as a candidate head, once during a single walk), so the total work is O(n).

The "only count from heads" filter is the load-bearing trick. Without it, walking from every value would be O(n²) in the worst case (one giant sequence).

O(n) solution

def longest_consecutive(nums: list[int]) -> int:
    """O(n). Only start counting from sequence heads (no predecessor in the set)."""
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 in s:
            continue        # not a sequence head; will be counted from a smaller starting point
        # x is a head: walk forward
        y = x
        while y + 1 in s:
            y += 1
        best = max(best, y - x + 1)
    return best

Trace

nums = [100, 4, 200, 1, 3, 2]
set  = {100, 4, 200, 1, 3, 2}

x=100: 99 not in s -> head. walk: 100 (101 not in s, stop). length = 1.
x=4:   3   IN  s -> not head, skip.
x=200: 199 not in s -> head. length = 1.
x=1:   0   not in s -> head. walk: 1 -> 2 -> 3 -> 4. length = 4.
x=3:   2   IN  s -> skip.
x=2:   1   IN  s -> skip.

return 4   (sequence [1, 2, 3, 4])

Reference: O(n log n) sort

def longest_consecutive_sort(nums: list[int]) -> int:
    """O(n log n) — sort, then count adjacent equal-or-plus-one."""
    if not nums: return 0
    nums = sorted(set(nums))
    best = cur = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1] + 1:
            cur += 1
            best = max(best, cur)
        else:
            cur = 1
    return best

Complexity

Variations worth knowing