019. Longest Consecutive Sequence

Why this mechanism works

A set gives constant expected membership checks, but expanding from every value would repeat long runs. Only expand x when x-1 is absent. That marks x as a sequence's unique start, so the total number of successful extension steps is bounded by the number of distinct values.

State and boundaries

values contains distinct input values. start is a candidate minimum; end is the first unconfirmed value beyond its currently verified consecutive run.

Protocol

1. Build a set.
2. Skip each value whose predecessor exists.
3. From each true start advance end while it exists.
4. Compare end-start with best.
5. Return best.

Visualization

{100,4,200,1,3,2}
starts: 100, 200, 1
1 -> 2 -> 3 -> 4 -> missing 5

Python implementation

def longest_consecutive(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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 longest_consecutive: values = set(nums)
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}

L3 longest_consecutive: best = 0
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=0

L4 longest_consecutive: for start in values:
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=0; start=1

L7 longest_consecutive: end = start
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=0; start=1; end=1

L9 longest_consecutive: end += 1
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=0; start=1; end=2

L9 longest_consecutive: end += 1
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=0; start=1; end=3

L9 longest_consecutive: end += 1
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=0; start=1; end=4

L9 longest_consecutive: end += 1
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=0; start=1; end=5

... 6 intermediate state changes omitted ...

L4 longest_consecutive: for start in values:
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=4; start=4; end=101

L4 longest_consecutive: for start in values:
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=4; start=200; end=101

L7 longest_consecutive: end = start
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=4; start=200; end=200

L9 longest_consecutive: end += 1
nums=[100, 4, 200, 1, 3, 2]; values={1, 100, 2, 200, 3, 4}; best=4; start=200; end=201

L2 longest_consecutive: values = set(nums)
nums=[]; values=set()

L3 longest_consecutive: best = 0
nums=[]; values=set(); best=0

Why the solution is correct

Every maximal consecutive sequence has exactly one value with no predecessor. Expansion from that value discovers its full length and no other start repeats its work. Taking the maximum over these disjoint sequences gives the answer.

Time and space

O(n) expected time and O(u) space. The nested-looking expansions visit each distinct value only once across all starts.

Common mistakes

Expanding from every value can be quadratic. Sorting is a valid O(n log n) alternative but is not the hash-state mechanism practiced here.

Reasoning card

Transfer exercise

Return the actual sequence, breaking equal-length ties by its smallest starting value.