Stamp album run

A collector's album is filled in the order stamps were acquired, not in catalogue order. The prize is a complete run, and finding the longest need not cost a sort.

The problem

Each stamp carries a catalogue number, and the album's index lists those numbers in acquisition order. The same number may appear twice: collectors keep swaps.

A run is a block of consecutive integers, every one present in the album: 411, 412, 413 is a run of length 3. Report the length of the longest run the collection contains. Duplicates do not lengthen a run — two copies of 77 cover only the number 77 — and the index is in no particular order.

Input. catalogue — a list of integers in acquisition order, possibly empty and possibly with repeats.

Output. An integer: the length of the longest run present, or 0 for an empty album.

Example.

catalogue = [412, 9, 411, 10, 413, 8, 11]   ->  4

The numbers 8, 9, 10, 11 form a run of four. The 411–413 block is a run of three, and 413 and 8 are unrelated despite sitting side by side in the index.

A second example, where a repeat could inflate a careless count:

catalogue = [77, 77, 78, 77]   ->  2

The album holds two distinct numbers, so the longest run is 2, not 3 or 4.

Constraints.

• 0 <= len(catalogue) <= 10^5
• -10^9 <= catalogue[i] <= 10^9

Hints

Approach

Brute force

Sort the index, then sweep it counting consecutive neighbours and skipping repeats. That costs O(n log n) — about 1.7 million comparisons for 100 000 stamps before the sweep starts — and the ordering it buys is used once and discarded.

The insight

Only a number whose predecessor is absent can begin a run, so testing that one condition before walking makes each run walked exactly once and the total work linear.

Put every catalogue number in a set, so membership costs average-case constant time. Scan the distinct numbers: when v - 1 is present, v sits inside a run that will be counted from its own start, so skip it. When v - 1 is absent, v is the smallest member of its run and the walk upward visits that run once. Summed over all runs the walking costs one step per distinct number, so the nested loop is linear despite how it looks.

Algorithm

1. Build a set from the catalogue; duplicates collapse on their own.
2. Set longest = 0.
3. For each number v in the set, skip it if v - 1 is in the set.
4. Otherwise set length = 1 and, while v + length is in the set, add one.
5. Keep the largest length, and return it.

Complexity

Time O(n) on average — each distinct number is tested once as a run start and visited at most once in a walk. Space O(n) for the set.

Solution

"""Stamp album run — longest consecutive block, walking each run once from its start."""


def solve(catalogue):
    held = set(catalogue)             # duplicates collapse; membership is O(1) on average
    longest = 0
    for number in held:
        if number - 1 in held:
            continue                  # invariant: only a run's smallest member is walked
        length = 1
        while number + length in held:
            length += 1
        longest = max(longest, length)
    return longest

TESTS = [
    (([412, 9, 411, 10, 413, 8, 11],), 4),
    (([77, 77, 78, 77],), 2),
    (([],), 0),
    (([500],), 1),
    (([4, 4, 4, 4],), 1),
    (([-3, -1, -2, 0, 5],), 4),
    (([20, 18, 16, 14],), 1),
]

Pitfalls

• Dropping the run-start test. Walking upward from every number stays correct but turns quadratic: an album holding 1 to 50 000 does about 1.25 billion membership tests instead of 50 000.
• Using the list instead of a set for membership. v + 1 in catalogue is a linear scan, so the method is O(n²) even with the run-start test in place.
• Iterating the list rather than the set. The same run start is processed once per copy, and a walk that counts list positions reports 3 for [77, 77, 78].
• Sorting without skipping equal neighbours. The fallback counts the repeat in [77, 77, 78] as a step and reports 3.

Variants

• Interfering channels — the same membership test with a fixed gap instead of a gap of one.
• When you need order too — the lesson on when the sorted fallback earns its log factor.