Problem Statement
Kth Missing Positive Number
You get a sorted list of positive whole numbers called arr, and a number k. Sorted means the numbers go from smallest to largest. Some positive numbers are not in the list. Those are the "missing" ones. Your job is to find the kth missing one. For example, in [2,3,4,7,11], the numbers that are missing are 1,5,6,8,9,10,12, and so on, so the 5th missing number is 9. The slow way is to count missing numbers one by one until you reach k. A faster way uses binary search. Binary search is like guessing a number between 1 and 100 where each guess cuts the range in half: you check the middle, throw away the half that can't hold the answer, and repeat. It works here because the list is sorted. Here is the trick that makes it work. At index i (counting from 0), the count of missing numbers that come before arr[i] is arr[i] - (i + 1). Why? If nothing were missing, the list would be 1,2,3,4,... and the value at index i would be exactly i+1. So if the real value is bigger than i+1, the gap tells you how many numbers got skipped.
Signals to notice
Brute force first
Iterate from 1 upward counting missing — O(n + k).
The key insight
Binary search: at index i, missing count = arr[i] - (i+1). Find leftmost index where missing ≥ k. Answer = k + left. O(log n).
Trace it on arr=[2,3,4,7,11], k=5
init: left=0, right=4 mid=2: arr[2]=4, missing=4-(2+1)=1 < 5 -> left=3 mid=3: arr[3]=7, missing=7-(3+1)=3 < 5 -> left=4 mid=4: arr[4]=11, missing=11-(4+1)=6 >= 5 -> right=3 left=4 > right=3 -> loop ends answer = k + left = 5 + 4 = 9
What must stay true
Without gaps, arr[i] would be i+1. The difference arr[i] - (i+1) counts missing numbers before position i.
Shape of the loop
left, right = 0, len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] - (mid+1) < k: left = mid + 1
else: right = mid - 1
return k + leftPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Off-by-one in the final answer — kth missing = k + left (the binary search result).