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
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int firstMissingSeq(std::vector<int> sequence) {
}Worked examples
| Call | Result |
|---|---|
firstMissingSeq(std::vector<int>{1, 2, 3}) | 0 |
firstMissingSeq(std::vector<int>{0, 1, 3}) | 2 |
firstMissingSeq(std::vector<int>{0, 1, 2}) | 3 |
firstMissingSeq(std::vector<int>{}) | 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 C++
int firstMissingSeq(std::vector<int> sequence) {
int length = (int) sequence.size();
std::vector<bool> present(length + 1, false);
for (int v : sequence) {
if (v >= 0 && v <= length) present[v] = true;
}
for (int i = 0; i <= length; i++) {
if (!present[i]) return i;
}
return length + 1;
}