Missing ranges: describe the gaps in a sorted list

You get a sorted list of distinct integers, all inside the range 0 to 99. Describe the numbers of that range that are missing, as a list of strings.

Interface

Unless you agree on a different interface with the interviewer, assume:

• missing_ranges(present: list[int]) -> list[str] — one string per maximal run of missing numbers [a, b], in increasing order. A run of three or more numbers is written "a->b". A run of one or two numbers is written out with commas, as "6" or "6,7". Return [] if nothing is missing.

Example

missing_ranges([0, 1, 5, 9, 99])   ->  ["2->4", "6->8", "10->98"]
missing_ranges([0, 2, 5, 99])      ->  ["1", "3,4", "6->98"]
missing_ranges([])                 ->  ["0->99"]
missing_ranges(list(range(100)))   ->  []

Constraints

• 0 <= len(present) <= 100. Values are sorted, distinct and inside [0, 99].

Clarifying questions

• Is the range always 0 to 99, or should it be parameters lo and hi?
• From what length does a run become "a->b"?
• Are the inputs guaranteed sorted and distinct?
• One string per run, or one string per missing number?

What a strong answer covers

• One pass that compares each value with the one before it, using sentinels lo - 1 and hi + 1 so the gaps at both ends need no special case.
• The formatting rule in one helper.
• O(n) time and O(1) extra space besides the output.
• Tests: empty input, a full range, gaps at the edges, gaps of exactly one, two and three numbers.

Follow-ups

• Make the bounds parameters, including negative ones.
• The input is unsorted or has duplicates.
• The range is huge (0 to 10^18) and the input arrives as a stream.