632. Kth Missing Positive Number
You are given arr, an array of positive integers sorted in strictly increasing order, and an integer k.
Imagine listing the positive integers 1, 2, 3, … and crossing out every one that appears in arr. The numbers that survive are the missing ones. Return the k-th missing positive integer, counting from the smallest.
For example, if arr = [1, 4, 9], the missing sequence starts 2, 3, 5, 6, 7, 8, 10, … — so the 3rd missing number is 5. A linear scan works; the follow-up is to answer in O(log n) using the sorted order.
Example 1:
Input: arr = [1, 4, 9], k = 3
Output: 5
Explanation: The missing positives are 2, 3, 5, 6, 7, 8, … — the third one is 5.
Example 2:
Input: arr = [3, 5], k = 2
Output: 2
Explanation: The missing positives are 1, 2, 4, 6, … — the second one is 2, before the array even starts.
Constraints:
- 1 ≤ arr.length ≤ 10⁴
- 1 ≤ arr[i] ≤ 10⁷
- arr is strictly increasing
- 1 ≤ k ≤ 10⁷
Hints:
How many positive integers are missing before arr[i]? The numbers 1..arr[i] hold arr[i] slots, and exactly i + 1 of them are taken by array elements — so arr[i] − (i + 1) are missing. That count never decreases as i grows.
Binary search the first index whose missing-count reaches k. If i indices come before that point, the answer is k + i — the k-th missing number shifted past the i array values that precede it. (If even the last element is short of k, the answer is k + n, beyond the array.)
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: arr = [1, 4, 9], k = 3
Expected output: 5