Given a strictly increasing array of positive integers arr and an integer k, return the k-th positive integer missing from the array. For arr = [2,3,4,7,11] and k = 5 the answer is 9.
If nothing were missing, arr[i] would equal i + 1. So the number of missing values before index i is arr[i] - (i + 1), and this count never decreases.
def find_kth_positive(arr, k):
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] - (mid + 1) < k:
lo = mid + 1
else:
hi = mid
return lo + kAfter the loop, lo elements of the array sit before the answer, so the answer is lo + k. O(log n) time.
Start with the O(n + k) walk, then derive the missing-count formula and point out it is monotonic, which is what makes binary search valid. Naming the monotonic property is the part interviewers want to hear. If you want practice explaining monotonic searches under time pressure, Linkjob AI's real-time interview helper can listen in on mock rounds. (Disclosure: I work on Linkjob AI.)