Problems › TypeScript › network
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.
firstMissingSeq(sequence: list<int>) → int
Where you start
function firstMissingSeq(sequence: number[]): number {
}Worked examples
| Call | Result |
|---|---|
firstMissingSeq([1,2,3]) | 0 |
firstMissingSeq([0,1,3]) | 2 |
firstMissingSeq([0,1,2]) | 3 |
firstMissingSeq([]) | 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 TypeScript
function firstMissingSeq(sequence: number[]): number {
const len = sequence.length;
const present = new Array<boolean>(len + 1).fill(false);
for (const v of sequence) {
if (v >= 0 && v <= len) present[v] = true;
}
for (let i = 0; i <= len; i++) {
if (!present[i]) return i;
}
return len + 1;
}