DSA Longest Consecutive Sequence

The problem

A consecutive sequence is a run of numbers where each value is one more than the previous value. The input is an unsorted list of numbers. The answer is the length of the longest such run hidden in it.

The run values need not sit next to each other in the list. Position in the list is irrelevant. Only the values themselves matter.

cases = [
    ([100, 4, 200, 1, 3, 2], 4),
    ([42, 4, 100, 3, 1, 41, 2, 43, 5], 5),
    ([0, 3, 7, 2, 5, 8, 4, 6, 0, 1], 9),
    ([], 0),
]
for nums, expected in cases:
    print("nums", nums, "longest run length:", expected)

Read one row at a time. The first list hides the run 1, 2, 3, 4 among larger numbers. The third list holds every value from 0 to 8, with 0 written twice, so its run has length 9.

Intuition: sort first, then scan

The first idea sorts the list. Sorting lines the values up in order. One scan then measures each run directly.

The idea works. Its cost is the trap. Sorting does far more comparisons than the scan that follows it, and the scan is the part that actually answers the question.

nums = [42, 4, 100, 3, 1, 41, 2, 43, 5]
arr = list(nums)
comparisons = 0
for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0:
        comparisons += 1
        if arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        else:
            break
    arr[j + 1] = key
print("sorted:", arr)
print("sorting comparisons:", comparisons)
best = 1
run = 1
for i in range(1, len(arr)):
    if arr[i] == arr[i - 1] + 1:
        run += 1
    elif arr[i] != arr[i - 1]:
        run = 1
    best = max(best, run)
print("longest run:", best)
print("scan steps after sorting:", len(arr) - 1)

One simple sort spent 25 comparisons before the eight-step scan began. Faster sorts spend fewer, but every sort spends more than the linear scan the problem actually needs. The set solution below skips sorting entirely.

Brute force: extend every number by scanning the list

The brute force tries each number as the start of a run. From a candidate, it looks for the next value, then the next. Each lookup scans the whole list from the beginning.

A membership scan is the hidden cost. The list gives no shortcut to a value, so finding one value can cost a full pass. A long run pays that pass again for every step upward.

nums = [42, 4, 100, 3, 1, 41, 2, 43, 5]
scans = 0

def contains(value):
    global scans
    for item in nums:
        scans += 1
        if item == value:
            return True
    return False

best = 0
for num in nums:
    length = 1
    current = num
    while contains(current + 1):
        length += 1
        current += 1
    best = max(best, length)
print("longest run:", best)
print("list items scanned:", scans)

Nine numbers produced well over a hundred scanned items. Every number was tried as a start, even numbers in the middle of a run. Every upward step re-scanned the list from index 0.

The optimal solution: a set, and starts only

A start is a number whose predecessor is missing, and counting upward from starts only, with membership tested in a set, visits each number once. That one sentence is the whole method.

The predecessor of a number is the number one smaller. A number with its predecessor present sits inside a run, so it is skipped as a start. The upward walk from the true start will pass through it anyway.

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for num in nums:
        if num - 1 in values:
            continue
        length = 1
        current = num
        while current + 1 in values:
            length += 1
            current += 1
        best = max(best, length)
    return best

cases = [
    ([100, 4, 200, 1, 3, 2], 4),
    ([42, 4, 100, 3, 1, 41, 2, 43, 5], 5),
    ([0, 3, 7, 2, 5, 8, 4, 6, 0, 1], 9),
    ([], 0),
]
for nums, expected in cases:
    result = longest_consecutive(nums)
    print("nums", nums, "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. The duplicate 0 in the third case changes nothing. The set holds one copy, and the run counts values, not list entries.

Walkthrough: runs inside [42, 4, 100, 3, 1, 41, 2, 43, 5]

The set holds all nine values. Three numbers have no predecessor present. Those three are the starts, and each one launches exactly one upward walk.

nums = [42, 4, 100, 3, 1, 41, 2, 43, 5]
values = set(nums)
for num in nums:
    if num - 1 in values:
        continue
    run = []
    current = num
    while current in values:
        run.append(current)
        current += 1
    print("start", num, "- run:", run, "- length:", len(run))

The walk from 1 collects five values. The walk from 41 collects three. The walk from 100 collects only itself. Together the walks touch nine values, one visit each.

Complexity

The set solution tests each number as a possible start once and steps upward once per number across all walks, so its time is O(n). The brute force re-scans the list for every upward step, so its time grows toward O(n^2) and beyond on long runs.

The set stores one entry per distinct value, so its space is O(n). The brute force stores no copy, so its extra space is O(1), paid for with far more scanning.

def set_steps(nums):
    values = set(nums)
    steps = 0
    for num in nums:
        if num - 1 in values:
            continue
        current = num
        while current in values:
            steps += 1
            current += 1
    return steps

for nums in [[1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7, 8], list(range(1, 17))]:
    print("values:", len(nums), "- upward steps:", set_steps(nums))

Counts beat clocks here. The step count equals the value count at every size. Doubling the input doubles the work, exactly as the formula says.

Edge cases and pitfalls

Counting from every number is the classic waste. The run gets recounted from each of its members, and the same values are visited again and again. The predecessor test is what prevents it.

Duplicates break naive sorted scans that reset a run on any repeated value. The set method never sees a duplicate at all. The copy in the set is the only copy that exists.

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for num in nums:
        if num - 1 in values:
            continue
        length = 1
        current = num
        while current + 1 in values:
            length += 1
            current += 1
        best = max(best, length)
    return best

print("empty list:", longest_consecutive([]))
print("single value:", longest_consecutive([7]))
print("all duplicates:", longest_consecutive([2, 2, 2]))
print("negative run:", longest_consecutive([-2, -1, 0, 5]))
print("no neighbours at all:", longest_consecutive([10, 30, 20]))
print("already sorted:", longest_consecutive([1, 2, 3]))

The no-neighbours row answers 1. Every value starts its own run there, and every run has length one. A longest length of 1 is still a correct answer, not a failure.