#1539
Kth Missing Positive Number
Easy Binary search on a derived value
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Given a strictly increasing array of positive integers, return the k-th positive integer that is missing from it.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the k-th positive number that's not in the array.
Why this works: before index i, arr[i] - (i+1) numbers are missing, and that count only grows. Binary search the first index where it reaches k.
Example: [2, 3, 4, 7, 11], k = 5
missing counts: 1, 1, 1, 3, 6first index with count ≥ 5 is 4answer 4 + 5 = 9
✦Hints open one at a time
Before index i, the count of missing numbers is arr[i] − (i + 1).
That count never decreases. Find the first index where it reaches k.
↗Approach
Binary search for the first i with arr[i] − i − 1 >= k. The answer is that index lo plus k (it falls just before arr[lo]).
</>Solution (Java)
class Solution {
public int findKthPositive(int[] arr, int k) {
int lo = 0, hi = arr.length;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] - mid - 1 < k) lo = mid + 1; // not enough missing yet
else hi = mid;
}
return lo + k;
}
}!Common mistake
Counting up one by one — O(n + k), fine for small inputs but misses the point.
Complexity
- Time: O(log n).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon