Longest consecutive run: expand only from starts

Account for which starts are redundant

Sort a copy, ignore duplicates, and count stretches with difference one. That baseline is straightforward O(n log n) time and O(n) auxiliary space in Python. A set supplies expected constant-time existence checks, but starting a forward walk at every value is still quadratic for [1, 2, ..., n]. Changing the container alone does not remove repeated work. Identify which values can be genuine starts: precisely those whose predecessor is absent.

For each start, increment an endpoint while the next consecutive value exists. Every finite maximal run has exactly one smallest element, whose predecessor is missing, so every run is considered. During a walk, every value from start up to but excluding the endpoint is present. The first absent endpoint proves the run is maximal. Non-starts cannot produce a longer answer than their own run's start, so skipping them preserves correctness.

The outer loop touches u distinct values. Across all inner loops, each distinct value is walked once, plus one failed lookup per run. That aggregate argument, not the number of nested loops, establishes expected O(n) time and O(u) auxiliary space. Iterate over the set, not the original list: repeated copies of the same start could otherwise retraverse a long run. Input order and set iteration order do not affect the maximum length.

Follow-up 1: return the run with the smallest start on ties

Predict the additional state: retain (start, length) rather than only length, and compare length first, then start. Never rely on set iteration order.

Returning just endpoints stays O(1) output. Materializing all values in the best run adds O(length) output, though it does not change the O(n) total bound.

Follow-up 2: answer after every insertion

Rebuilding the set and rescanning after every arrival costs quadratic total work. Use disjoint-set union: each new distinct value starts as a singleton component, then unions with existing immediate neighbors; component size is run length.

Path compression and union by size give near-constant amortized insertion, but deleting an interior value can split a run and needs a different design. A senior candidate proves the aggregate bound and tests duplicate starts. A lead candidate specifies insertion/deletion semantics and whether integer adjacency is meaningful across shards before adopting a dynamic connectivity representation.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/08-longest-consecutive
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def _integers(values):
    if not isinstance(values, (list, tuple)) or any(type(x) is not int for x in values):
        raise ValueError("expected a list or tuple of integers, excluding bool")

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

import itertools
import unittest
from solution import longest_consecutive

class ConsecutiveTests(unittest.TestCase):
    def test_boundaries(self):
        self.assertEqual(longest_consecutive([100, 4, 200, 1, 3, 2, 2]), 4)
        self.assertEqual(longest_consecutive([-1, 1, 0]), 3)
        self.assertEqual(longest_consecutive([]), 0)
        self.assertEqual(longest_consecutive([1] * 200 + list(range(1, 200))), 199)
        with self.assertRaises(ValueError):
            longest_consecutive(["1"])

    def test_sorted_oracle(self):
        for n in range(6):
            for nums in itertools.product(range(-2, 3), repeat=n):
                ordered = sorted(set(nums))
                best = run = 0
                previous = None
                for value in ordered:
                    run = run + 1 if previous is not None and value == previous + 1 else 1
                    best = max(best, run)
                    previous = value
                self.assertEqual(longest_consecutive(nums), best)

if __name__ == "__main__":
    unittest.main()