EasyNeetCode150ArrayBinary Search
Kth Missing Positive Number
Find kth missing positive integer.
Examples
Input
arr = [2,3,4,7,11], k = 5
Output
9
Missing: 1,5,6,8,9. 5th is 9.
Constraints
- •
1 <= arr.length <= 1000 - •
1 <= arr[i] <= 1000 - •
arr is strictly increasing
Approaches
Check each number.
CodeT: O(n+k) | S: O(1)
Find position where arr[i]-i-1 >= k.
CodeT: O(log n) | S: O(1)
def findKthPositive(arr, k):
l,r=0,len(arr)-1
while l<=r:
m=(l+r)//2
if arr[m]-m-1<k: l=m+1
else: r=m-1
return l+kSame approach.
CodeT: O(log n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Linear Scan | O(n+k) | O(1) | Check each number. |
| Binary Search | O(log n) | O(1) | Find position where arr[i]-i-1 >= k. |
| Binary Search Optimized | O(log n) | O(1) | Same approach. |
Linear Scan
T: O(n+k)S: O(1)
Check each number.
Binary Search
T: O(log n)S: O(1)
Find position where arr[i]-i-1 >= k.
Binary Search Optimized
T: O(log n)S: O(1)
Same approach.
Common Mistakes
Not handling first missing positive
Off-by-one in formula
Wrong binary search bounds