Unlogged Wildlife Tags
Kth missing positive integer from a strictly increasing array
A wildlife survey uses positive integer tag numbers starting at 1. Its observation ledger contains tags, the tag numbers that have been recorded, in strictly increasing order.
A tag number is unlogged if it does not appear in the ledger. Consider all unlogged positive integers in increasing order, including numbers larger than the last recorded tag.
Return the kth unlogged tag number, where k is one-based. An empty ledger means every positive integer is unlogged.
Examples
Example 1
Input: tags = [2,3,7,8], k = 4 Output: 6
The unlogged tag numbers begin 1, 4, 5, 6, 9, and so on. The survey asks for the fourth one.
Example 2
Input: tags = [1,2,3], k = 2 Output: 5
All tags from 1 through 3 are logged, so the unlogged sequence starts immediately after them.
Example 3
Input: tags = [], k = 1 Output: 1
With no recorded tags, the unlogged sequence is simply all positive integers in order.
Constraints
- 0 <= tags.length <= 4000
- 1 <= tags[i] <= 1,000,000,000
- tags is strictly increasing.
- 1 <= k <= 1,000,000,000
The intended solution uses O(log(n + 1)) time and O(1) extra space, where n is the ledger length.
Hints
Show hint 1Hint 1
At index i, how many positive integers smaller than tags[i] are absent from the ledger?
Show hint 2Hint 2
Those missing counts never decrease. Binary search for the first index whose missing count is at least k, allowing the search to end past the array.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you answer many different k queries against the same ledger?
- How would you adapt the missing-count formula if valid tag numbers started at a given positive integer instead of 1?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem