Kth Missing Positive Number
easyTime: O(log n)Space: O(1)
Recognize the pattern
kth missing positive integersorted array with gapsbinary search on missing count
Brute force idea
Iterate from 1 upward counting missing — O(n + k).
Better approach
Binary search: at index i, missing count = arr[i] - (i+1). Find leftmost index where missing ≥ k. Answer = k + left. O(log n).
Key invariant
Without gaps, arr[i] would be i+1. The difference arr[i] - (i+1) counts missing numbers before position i.
Watch out for
Off-by-one in the final answer — kth missing = k + left (the binary search result).