Longest Consecutive Sequence

Problem

Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed. A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

You must write an algorithm that runs in $O(n)$ time.

Example 1

Input:  nums = [2, 20, 4, 10, 3, 4, 5]
Output: 4          # [2, 3, 4, 5]

Example 2

Input:  nums = [0, 3, 2, 5, 4, 6, 1, 1]
Output: 7          # [0, 1, 2, 3, 4, 5, 6]

Constraints

• 0 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9

Thinking

• Brute force idea: treat every element as the start of a sequence and count up with x + 1 in nums. With a list lookup that’s $O(n^3)$; with a set it’s still $O(n^2)$ because every element of a long run re-walks the rest of the run.
• Sorting idea: sort, then scan once counting runs (skip duplicates, reset on a gap): $O(n \log n)$. Correct and simple, but breaks the $O(n)$ requirement.
• Key insight: only walk from the start of a sequence: x is a start iff x - 1 is not in the set. Then each number is visited once by the for loop and at most once by a while walk, so the total work is $O(n)$ (amortized, even though there’s a nested loop).
• Loop over the set, not the list. With duplicates of a start value ([0, 0, 0, ..., 0, 1, 2, ..., m]) looping over nums re-walks the same run once per copy: $O(n^2)$.
• Edge cases to remember: empty array → 0; duplicates ([1, 1] → 1, they don’t extend a run); negatives and runs crossing 0; all elements isolated → 1; values near $\pm 10^9$ (fine in Python, x + 1 can’t overflow).

Solution

Approach A — my version (hash set, walk from sequence starts)

Complexity: Time $O(n)$ · Space $O(n)$. This already is the optimal algorithm, and it loops over the set, so duplicates can’t make it quadratic. Small things only:

1. n + 1 in nums_set skips singletons before any walking. It costs an extra lookup per start but saves the while setup and the max() call, and on sparse data (most numbers isolated) that makes mine the fastest version (see section 5). The price is the len == 0 guard and counter = 1.
2. start is really the current end of the run, and temp_counter duplicates what start - n + 1 already tells you. One variable is enough.

The code is unchanged except for the signature and comments.

def longest_consecutive_mine(nums: list[int]) -> int:
    if len(nums) == 0:                                   # needed because counter starts at 1
        return 0
    nums_set = set(nums)
    counter = 1

    for n in nums_set:                                   # good: set, not list (no duplicate re-walks)
        if n - 1 not in nums_set and n + 1 in nums_set:  # skips singletons cheaply (a speed win)
            start = n                                    # really the current end of the run
            temp_counter = 1
            while start + 1 in nums_set:
                temp_counter += 1
                start += 1
            counter = max(counter, temp_counter)
    return counter

Approach B — sort and scan

Complexity: Time $O(n \log n)$ · Space $O(n)$ for the sorted copy. Sort, then count runs: same value → skip, +1 → extend, anything else → reset. Doesn’t meet the $O(n)$ requirement, but it’s the natural first answer and useful when memory for a set is tight (sorting in place needs no extra hash table).

def longest_consecutive_sort(nums: list[int]) -> int:
    if not nums:
        return 0
    nums = sorted(nums)  # copy: don't mutate the caller's list
    longest = current = 1
    for prev, x in zip(nums, nums[1:]):
        if x == prev:
            continue                   # duplicate: neither extends nor breaks the run
        if x == prev + 1:
            current += 1
            longest = max(longest, current)
        else:
            current = 1
    return longest

Approach C — hash set, walk only from starts ✅ best practice

Complexity: Time $O(n)$ · Space $O(n)$. Approach A, tidied: no special cases, one walking variable. The if x - 1 not in num_set line is the whole trick; it guarantees each run is walked exactly once.

def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)
    longest = 0
    for x in num_set:              # the set, so duplicates don't cause re-walks
        if x - 1 not in num_set:   # x starts a run
            end = x
            while end + 1 in num_set:
                end += 1
            longest = max(longest, end - x + 1)
    return longest

Approach D — hash map of run lengths at the boundaries (one pass)

Complexity: Time $O(n)$ · Space $O(n)$. For each new x, look up the run lengths ending at x - 1 (left) and starting at x + 1 (right). The merged run has length left + right + 1; store it at x and at the two new boundaries x - left and x + right. Only boundaries need to be correct, so it’s $O(1)$ per element. Same idea as union-find on consecutive numbers; useful when numbers arrive as a stream.

def longest_consecutive_boundary(nums: list[int]) -> int:
    run = {}  # x -> length of the run x belongs to (only reliable at run boundaries)
    longest = 0
    for x in nums:
        if x in run:
            continue                   # duplicate
        left = run.get(x - 1, 0)
        right = run.get(x + 1, 0)
        length = left + right + 1
        run[x] = run[x - left] = run[x + right] = length
        longest = max(longest, length)
    return longest

Scratch / Experiments

Two inputs at the max size $n = 10^5$:

• random: values from the full range $\pm 10^9$, so almost every run has length 1;
• one run: range(n) shuffled, so one run of length $n$ (the while walk does all the work).

Measured on my machine:

• A beats C on random data. Almost every number is a run of length 1. C still calls max() and computes end - x + 1 for each one; A’s n + 1 in nums_set check drops them first. A Python function call costs more than a set lookup, so the filter pays off. On one long run there’s only one start, so the filter does nothing and the two are about even.
• Sorting (B) is close despite $O(n \log n)$: sorted is Timsort in C and $\log_2 10^5 \approx 17$ is small. Big-O says how it grows, not which wins at this size.
• D is the slowest, despite being one pass: it does ~4 dict operations per element and allocates a dict entry for each one.
• The trap: looping over the list is ~800× slower (122 ms vs 155 μs) on just 4000 elements, because the run of 2000 is re-walked once for each of the 2000 copies of 0.

The last block shows the trap from section 2: looping over nums instead of the set, with many copies of a run’s start. Shrunk to $m = 2000$ copies + a run of 2000 because it’s quadratic.

import random

random.seed(0)
n = 100_000
random_nums = [random.randint(-10**9, 10**9) for _ in range(n)]
one_run = list(range(n))
random.shuffle(one_run)

for label, data in [("random", random_nums), ("one run", one_run)]:
    print(f"--- {label}")
    for fn in APPROACHES:
        print(f"{fn.__name__:30s}", end=" ")
        %timeit -n 5 -r 3 fn(data)

def longest_consecutive_loop_list(nums: list[int]) -> int:
    num_set = set(nums)
    longest = 0
    for x in nums:                 # SLOW: list, so each duplicate start re-walks its run
        if x - 1 not in num_set:
            end = x
            while end + 1 in num_set:
                end += 1
            longest = max(longest, end - x + 1)
    return longest

m = 2000
trap = [0] * m + list(range(m))    # m copies of the start 0, run length m
for fn in (longest_consecutive, longest_consecutive_loop_list):
    print(f"{fn.__name__:30s}", end=" ")
    %timeit -n 3 -r 3 fn(trap)

Takeaways

• Pattern: “longest run of consecutive values in $O(n)$, original order doesn’t matter” → put everything in a hash set and only start counting at run starts (x - 1 not in set). A nested while is still $O(n)$ total when each element is walked at most once: argue it by amortization, not by counting loop depth.
• Mistakes I made:
  • None in correctness or Big-O: my solution was already the optimal approach and correctly looped over the set.
  • The n + 1 in nums_set filter is a real optimization (it skips max() for every isolated number), but it forced a len == 0 guard and counter = 1. In an interview, write the simple version (longest = 0, no guard) first; add the filter as a micro-optimization.
  • Two variables (start, temp_counter) tracked the same thing. Keep one (end) and compute the length as end - x + 1.
  • Remember why iterating the set matters: over the list, duplicates of a start value make it $O(n^2)$.
• Related problems: Contains Duplicate (#217, the same “hash set for $O(1)$ membership” step), Binary Tree Longest Consecutive Sequence (#298, the same “+1 chain” on a tree), Number of Islands (#200) / Graph Valid Tree (#261) (union-find, the idea behind Approach D), Missing Number (#268) and First Missing Positive (#41) (reasoning about which values are present).