Kth Number Missing From a List
Problem
Ticket numbers are handed out from 1 upwards, and nums lists the ones that have been used, strictly increasing and all positive. Return the k-th smallest positive number that does not appear in nums, where k is at least 1. Aim for a solution faster than walking through the numbers one by one.
Examples
Input: nums = [2, 3, 4, 7, 11], k = 5
Output: 9
Why: the missing numbers are 1, 5, 6, 8, 9, 10, ...Input: nums = [1, 2, 3, 4], k = 2
Output: 6
Why: nothing is missing inside the list, so the answer lies past its endInput: nums = [], k = 4
Output: 4
Why: edge case, with nothing used, the k-th missing number is k itselfHints
0 / 3
If nothing were missing, the value at index i would be i + 1. The gap between the real value and i + 1 tells you something useful.
nums[i] minus (i + 1) is the number of missing values below nums[i], and it never decreases as i grows, so it can be binary searched.
Find the first index where that count reaches k. If that index is lo, exactly lo list values lie below the answer, so the answer is lo + k.
Solution
At index i the list has used i + 1 numbers, so nums[i] minus (i + 1) numbers below nums[i] are missing, and that count never decreases along the list. Binary search finds lo, the first index where at least k numbers are missing, or the list length if there is none. The answer then sits after exactly lo used numbers and is the k-th number not among them, which is lo + k. Time is O(log n) and space is O(1).
def kth_missing(nums, k):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] - (mid + 1) < k: # fewer than k missing below nums[mid]
lo = mid + 1
else:
hi = mid
return lo + k # lo used numbers lie below the answer
print(kth_missing([2, 3, 4, 7, 11], 5)) # -> 9
print(kth_missing([1, 2, 3, 4], 2)) # -> 6
print(kth_missing([], 4)) # -> 4
print(kth_missing([5, 6, 7], 3)) # -> 3Stuck on the idea rather than the code? Binary Search covers it.