Kth Missing Positive Number
easyTime: O(log n)Space: O(1)
Signals to notice
kth missing positive integersorted array with gapsbinary search on missing count
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).
What must stay true
Without gaps, arr[i] would be i+1. The difference arr[i] - (i+1) counts missing numbers before position i.
Easy way to go wrong
Off-by-one in the final answer — kth missing = k + left (the binary search result).