Longest Consecutive Sequence

Most people solve this problem by sorting, and sorting is a perfectly good answer — unless the interviewer says "in O(n)". Then it becomes one of the most surprising problems in this section: a loop inside a loop that is nevertheless linear, because of one if statement.

It is also the best example of a set used as an instant membership test rather than a duplicate detector. The set does not remember what you have seen; it remembers what exists, so you can ask "is v + 1 anywhere in the input?" in one step.

The problem

You are given an unsorted list of integers. Return the length of the longest run of consecutive integers v, v + 1, …, v + L − 1 whose values all appear somewhere in the list. The values can be in any positions. Your solution should run in O(n) time.

• [100, 4, 200, 1, 3, 2] → 4, for the run 1, 2, 3, 4.
• [9, 1, 8, 3, 7, 2, -1, 0] → 5, for the run −1, 0, 1, 2, 3. (7, 8, 9 is a run of 3.)

Constraints: 0 ≤ n ≤ 10⁵, values between −10⁹ and 10⁹, duplicates allowed.

Clarifying questions

• Do duplicates count twice? No. [1, 2, 2, 3] has a run of length 3.
• Empty list? Return 0.
• Negative numbers? Yes; a run can cross zero, as in the second example.
• Must it be O(n)? Assume yes — it is what separates this problem from a sorting exercise.

Approach 1: count upward from every value

For each value, count how far you can go up — v + 1, v + 2, … — checking whether each is in the list.

1def longest_consecutive_brute(numbers: list[int]) -> int:2    """From every value, count upward, searching the list each time."""3    longest = 04    for value in numbers:5        length = 16        while value + length in numbers:      # 'in' on a list is a linear scan7            length += 18        longest = max(longest, length)9    return longest

Time: O(n³) in the worst case. Space: O(1).

Why cubed? Take a single run of n values. The walk from the smallest value takes n steps, from the next n − 1 steps, and so on: about n²/2 steps. Each step is an in on a list, which scans up to n elements. At n = 10⁵ that is hopeless.

Approach 2: sort, then count runs

1def longest_consecutive_sorted(numbers: list[int]) -> int:2    """Sort, then count runs, skipping duplicates."""3    if not numbers:4        return 05    ordered = sorted(numbers)6    longest = current = 17    for previous, value in zip(ordered, ordered[1:]):8        if value == previous:9            continue                      # a duplicate neither extends nor breaks the run10        if value == previous + 1:11            current += 112        else:13            current = 114        longest = max(longest, current)15    return longest

Time: O(n log n) for the sort. Space: O(n) for the sorted copy.

This is what most candidates write, and it is correct and fast in practice — 10⁵ values sort in a few milliseconds. The duplicate line is the part people forget: without it, [1, 2, 2, 3] resets the run at the second 2 and returns 2. But it is O(n log n), and the problem asks for O(n).

The key insight

Put every value in a set. Now "is v + 1 in the input?" costs O(1), so walking a run upward is cheap. The danger is walking the same run many times: starting from 1, then from 2, then from 3, each walk repeating the rest of the run. That is O(n²) on a single long run, even with the set.

The fix is to walk only from the start of a run. A value v starts a run exactly when v − 1 is not in the set. From 1 in the first example, 0 is missing, so 1 starts a run and we walk 1, 2, 3, 4. From 2, 3 and 4, the value below is present, so we skip them immediately.

Now count the total work. Every value is checked once as a possible start: one lookup. And every value is walked over at most once in total, because it belongs to exactly one run, and that run is walked once, from its start. So the lookups add up to about 2n, not n². The inner while looks alarming, but its total cost across the whole outer loop is O(n).

Real numbers: on a single run of 10,000 values (1 to 10,000), the version with the start guard does 20,000 set lookups. Without the guard, it does 50,005,000.

Approach 3: a set, walking only from run starts

1def longest_consecutive(numbers: list[int]) -> int:2    """Walk upward only from values that start a run."""3    values = set(numbers)4    longest = 05    for value in values:                  # iterate the set, not the list6        if value - 1 in values:7            continue                      # not a run start8        length = 19        while value + length in values:10            length += 111        longest = max(longest, length)12    return longest

Dry run on [100, 4, 200, 1, 3, 2]. A Python set does not keep input order; this is the order CPython actually visited the values in when we ran it. The answer does not depend on the order.

Three values were skipped with one lookup each. The walk from 1 visited 2, 3 and 4, and nothing visited them again.

Time: O(n) on average — building the set is O(n), and the loop does about 2n lookups in total. Space: O(n) for the set.

Edge cases

• Empty list: the set is empty, the loop never runs, longest stays 0.
• All duplicates: [7, 7, 7] becomes the set {7}; one run of length 1.
• Negatives and zero: [9, 1, 8, 3, 7, 2, -1, 0] → 5. Nothing special: −1 − 1 = −2 is simply absent.
• Iterating the list instead of the set: with many copies of a run start, such as 50,000 copies of 1 followed by 2 to 50,001, each copy of 1 passes the guard and walks the whole run: O(n²). Iterating the set visits each distinct value once.

Follow-ups

• Return the run itself: also remember the start value of the best run, then return list(range(best_start, best_start + longest)).
• Values arrive one at a time and you must report the longest run after each: keep a map from value to run length, maintained only at run ends. When x arrives (and is new), read left = length[x − 1] and right = length[x + 1] (0 if missing), set total = left + right + 1, and write total at x itself and at the two new ends, x − left and x + right. Storing x also lets you ignore a repeat of it. O(1) per insert.
• Union-find: join each value with value + 1 when both exist; the largest component is the answer. Also near O(n), but more code for the same result.