Kth Missing Positive Number
EasyMissing before a[i] = a[i] − (i+1)
Use halving to jump straight to where the k-th skipped number would be.
The idea
At index i, exactly a[i] − (i+1) positives are missing before it — a monotone count. Binary search where the kth missing falls.
lo
hi
2
3
4
7
11
0
1
2
3
4
Step 1 of 5. Find the 5th missing positive. Missing before a[i] = a[i] − (i+1). Values: 2, 3, 4, 7, 11. Pointers: lo at index 0, hi at index 4.
1/5
Optimal
timeO(log n)spaceO(1)
Answer = lo + k.
1let lo = 0, hi = n - 1;2while (lo <= hi) {3 const mid = (lo + hi) >> 1;4 if (a[mid] - (mid + 1) < k) lo = mid + 1;5 else hi = mid - 1;6}7return lo + k;Input
- array
- [2, 3, 4, 7, 11]
Memory
- lo
- = 0 [2]
- hi
- = 4 [11]
- mid
- —
- missing
- —
Output
- 5th missing
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [2, 3, 4, 7, 11], k = 5
- Output:
- 9
- Explanation:
- Missing are 1,5,6,8,9,... the 5th is 9.
Example 2
- Input:
- nums = [1, 2, 3, 4], k = 2
- Output:
- 6
- Explanation:
- Missing start at 5, so the 2nd is 6.
Example 3
- Input:
- nums = [5, 6, 7], k = 3
- Output:
- 3
- Explanation:
- 1,2,3 are missing → the 3rd is 3.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.