Longest Consecutive Sequence: Longest Run of Consecutive Integers in O(n)

Problem

Given an unsorted list of integers, return the length of the longest sequence of values v, v+1, v+2, ... that are all present in the list. The values need not be adjacent in the list, and duplicates do not extend a run. Aim for O(n) time. This is widely known as LeetCode 128, Longest Consecutive Sequence.

The list may be empty and may hold up to 10^5 values in the signed 32-bit range.

Examples

nums = [10, 4, 21, 6, 5, 3]   ->  4    (3, 4, 5, 6)
nums = [7, 7, 8]              ->  2    (7, 8; the second 7 does not count)
nums = []                     ->  0
nums = [-1, 1, 0]             ->  3    (-1, 0, 1)

Approach 1: brute force

Sort, then scan once, extending the current run when the next distinct value is one more than the previous and resetting otherwise.

def longest_consecutive_sort(nums):
    if not nums:
        return 0
    vals = sorted(set(nums))
    best = run = 1
    for a, b in zip(vals, vals[1:]):
        run = run + 1 if b == a + 1 else 1
        best = max(best, run)
    return best

Complexity: O(n log n) time, O(n) space. (The truly naive version, starting a run from every value and testing membership in the list, is O(n³).)

Approach 2: optimal

Key insight: only count upward from values that start a run, meaning v - 1 is absent. Every other value is skipped in the outer loop, so each value is touched a bounded number of times.

Walkthrough on [10, 4, 21, 6, 5, 3], set = {3, 4, 5, 6, 10, 21}:

v	v - 1 in set?	Action	Run length
10	no	count 10 → 11 missing	1
4	yes	skip
21	no	count 21 → 22 missing	1
6	yes	skip
5	yes	skip
3	no	count 3, 4, 5, 6 → 7 missing	4

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for v in values:
        if v - 1 not in values:
            end = v
            while end + 1 in values:
                end += 1
            best = max(best, end - v + 1)
    return best

Iterate over the set, not the original list: with many duplicates of a run start, looping over the list would redo the same count once per copy.

Complexity: O(n) average time, O(n) space. The inner loop runs only from run starts, and runs do not overlap, so across the whole algorithm it advances at most n times in total.

Tests

import random

for f in (longest_consecutive, longest_consecutive_sort):
    assert f([10, 4, 21, 6, 5, 3]) == 4
    assert f([7, 7, 8]) == 2                         # duplicates
    assert f([]) == 0                                # empty
    assert f([42]) == 1                              # single element
    assert f([-1, 1, 0]) == 3                        # negatives
    assert f([5, 5, 5]) == 1                         # all equal
    assert f([2**31 - 1, -2**31]) == 1               # extremes, not consecutive
    assert f([1, 3, 5, 7]) == 1                      # no runs

assert longest_consecutive(list(range(100_000, 0, -1))) == 100_000   # large, reversed

random.seed(9)
for _ in range(300):
    arr = [random.randint(-10, 10) for _ in range(random.randint(0, 15))]
    assert longest_consecutive(arr) == longest_consecutive_sort(arr)

Edge cases and pitfalls

• Without the v - 1 not in values check, the algorithm counts from every value and becomes O(n²) on a long run.
• Empty input returns 0, not 1.
• Duplicates must not lengthen a run; using a set handles that automatically.
• A while loop that walks downward and upward from every value works too but needs a visited set to stay O(n).

Where this shows up in data engineering

This is the “gaps and islands” problem from SQL: find runs of consecutive dates on which a user was active, or consecutive sequence numbers in a stream to detect missing messages. In SQL the standard trick is value - ROW_NUMBER() OVER (ORDER BY value), which is constant within each island.