The first missing sequence number
A reliable-transport layer assigns monotonically increasing sequence numbers, but packets can arrive out of order or be lost. Find the lowest number starting from zero that has not been seen.
- Return the smallest non-negative integer that is absent from the sequence.
- The sequence may contain duplicates.
- An empty sequence means zero has never arrived: return 0.
first_missing_seq(sequence: list<int>) → int
Where you start
def first_missing_seq(sequence: list[int]) -> int:
Worked examples
| Call | Result |
|---|---|
first_missing_seq([1, 2, 3]) | 0 |
first_missing_seq([0, 1, 3]) | 2 |
first_missing_seq([0, 1, 2]) | 3 |
first_missing_seq([]) | 0 |
Hint
Build a boolean presence array covering 0 through the list length, mark every value that falls in range, then scan for the first gap.
Reference solution in Python
def first_missing_seq(sequence: list[int]) -> int:
length = len(sequence)
present = [False] * (length + 1)
for v in sequence:
if 0 <= v <= length:
present[v] = True
for i in range(length + 1):
if not present[i]:
return i
return length + 1