Longest run of consecutive ticket numbers

Arrays, strings and hash maps Mid-level Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

Which change keeps this O(n)?

Python 3.13
def longest(nums: list[int]) -> int:
    s, best = set(nums), 0
    for x in s:
        y = x
        while y + 1 in s:
            y += 1
        best = max(best, y - x + 1)
    return best
print(longest([3, 1, 2]))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A Start counting only when x - 1 not in s

Right: each run is then walked once, from its smallest number.

The guard turns many overlapping walks into exactly one walk per run, so total steps stay proportional to the number of distinct values.

Why not the others?
  • B Sort the set before the loop. That adds O(n log n) and does not stop repeated walks.
  • C Use a list instead of a set. Membership checks become O(n) each, making it slower.

30-second answer

Put the numbers in a set. A number starts a run only if number - 1 is missing; from each start, count upward while the next number is present. Every number is visited by at most one upward walk, so the work is O(n) on average, versus O(n log n) for sorting first. The set takes O(n) space.

Practise saying it · 45 s. No recording, just a timer

Explain why the set-based scan is linear.

Say your answer out loud, then check which of these points you covered:

  • Set for O(1) membership
  • Start only at run starts
  • Amortized one walk per run

Deep dive

The 'only start where x - 1 is missing' rule is what keeps it linear: without it, every element would walk its own run and the cost could reach O(n²).

Duplicates disappear in the set, which is what you want: a repeated 8 does not lengthen 7, 8, 9.

Sorting and scanning is simpler to say and fine for small inputs; mention it as the baseline.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def longest_run(tickets: list[int]) -> int:
    s = set(tickets)
    best = 0
    for x in s:
        if x - 1 in s:
            continue
        end = x
        while end + 1 in s:
            end += 1
        best = max(best, end - x + 1)
    return best

Common mistakes

  • Walking upward from every number, not just run starts, which is quadratic on a long run.
  • Counting duplicates as extra length after sorting.

Senior take & follow-ups

Interviewers like hearing why the inner while loop does not make it quadratic. Give the amortized argument in one sentence.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you return the run itself?

    Show hint

    Remember the start with the best length and rebuild it as range(start, start + best).

  2. What if numbers arrive one at a time?

    Show hint

    Union-find over neighbours, or a map of run endpoints updated on each insert.

What each operation costs: Arrays · Dynamic Arrays · Hash Table · Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.