Medium · Missing-Count Binary Search
Understand → Visualise → Practice.
Given strictly increasing positive values, return the kth positive integer absent from the array.
Before index i, nums[i] − (i + 1) positive integers are missing. Binary search for the first index where that count reaches k.
missing(i) = nums[i] − i − 1, which never decreases.
Find the first index lo where missing(lo) ≥ k.
The kth missing number is lo + k.
O(log n) time and O(1) space.
Counting up from 1 and skipping present values is O(n + k).
Read the full guides first: Sorting Algorithms and Their Trade-offs, Binary Search and Boundary Finding.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.