Kth Missing Positive Number

Kth Missing Positive Number

1. What is this problem about?

The Kth Missing Positive Number interview question asks you to find the $k^{th}$ positive integer that is not present in a given sorted array. For example, in [2, 3, 4, 7, 11] with $k=5$, the missing numbers are 1, 5, 6, 8, 9, 10... the $5^{th}$ one is 9.

2. Why is this asked in interviews?

Companies like Uber and Meta ask this to see if you can optimize a linear search ($O(N)$) into a logarithmic search ($O(\log N)$). Because the array is sorted, you can calculate how many numbers are missing before any given index. This is a classic Binary Search interview pattern.

3. Algorithmic pattern used

This problem is best solved using Binary Search on Indices.

1. The Core Insight: At index i, the value should be i + 1 if no numbers were missing.
2. Missing Count: The number of missing integers before arr[i] is arr[i] - (i + 1).
3. Search: Use binary search to find the smallest index left such that arr[left] - (left + 1) >= k.
4. Formula: The $k^{th}$ missing number is left + k.

4. Example explanation

arr = [2, 3, 4, 7, 11], k = 5

• index 0 (2): missing $2 - 1 = 1$.
• index 3 (7): missing $7 - 4 = 3$.
• index 4 (11): missing $11 - 5 = 6$. Binary search finds that at index 4, the missing count (6) first exceeds $k=5$. The $k^{th}$ missing number is left + k = 4 + 5 = 9.

5. Common mistakes candidates make

• Linear Simulation: Counting one by one, which is $O(N+K)$. This is acceptable for small constraints but not optimal.
• Off-by-one: Errors in the formula relating the index, the value, and the missing count.
• Handling large k: Forgetting that the $k^{th}$ missing number might be larger than any element in the array.

6. Interview preparation tip

Whenever you have a sorted array and a question about "gaps" or "missing items," try to define a property f(i) that counts gaps up to index i. If f(i) is monotonic, you can always use Binary Search. This is a powerful Array interview pattern.