Kth Missing Positive Number
Problem
Given a sorted array of strictly increasing positive integers and an integer k, return the kth positive integer missing from the array.
arr = [2, 3, 4, 7, 11], k = 59def find_kth_positive(arr, k):
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] - mid - 1 < k:
lo = mid + 1
else:
hi = mid
return lo + kfunction findKthPositive(arr, k) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] - mid - 1 < k) lo = mid + 1;
else hi = mid;
}
return lo + k;
}class Solution {
public int findKthPositive(int[] arr, int k) {
int lo = 0, hi = arr.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (arr[mid] - mid - 1 < k) lo = mid + 1;
else hi = mid;
}
return lo + k;
}
}int findKthPositive(vector<int>& arr, int k) {
int lo = 0, hi = arr.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] - mid - 1 < k) lo = mid + 1;
else hi = mid;
}
return lo + k;
}Explanation
The clever observation is that at any index i, the count of positive integers missing before arr[i] is exactly arr[i] - i - 1 — because a gap-free array would hold i + 1 at that spot. This "missing count" only grows as i grows, so we can binary-search it.
We look for the first index where the missing count reaches k. If arr[mid] - mid - 1 < k, not enough numbers are missing yet, so we go right with lo = mid + 1. Otherwise we have enough, so we keep the left side with hi = mid.
When the loop ends, lo is the count of array elements sitting before the answer. The k-th missing number is simply lo + k: we step k past those lo present values.
Example: arr = [2,3,4,7,11], k = 5. The missing numbers are 1, 5, 6, 8, 9, … The search converges to lo = 4, so the answer is 4 + 5 = 9, the 5th missing number.
Binary search over the indices makes this O(log n), faster than walking through the gaps one at a time.