Problem Overview
You are given a sorted array of distinct positive integers, arr[], and a positive integer k.
Your task is to find the kth missing positive number that does not appear in arr[].
Example 1
Input
arr = [2, 3, 4, 7, 11]
k = 5
Output
9
Explanation
Missing numbers:
1, 5, 6, 8, 9, 10, ...
The 5th missing number is:
9
Example 2
Input
arr = [1, 2, 3]
k = 2
Output
5
Explanation
Missing numbers:
4, 5, 6, ...
The 2nd missing number is:
5
Example 3
Input
arr = [3, 5, 9, 10, 11, 12]
k = 2
Output
2
Explanation
Missing numbers:
1, 2, 4, 6, ...
The 2nd missing number is:
2
Constraints
Understanding the Problem
We need to determine the kth positive number that is missing from the sorted array.
Example
arr = [2, 3, 4, 7, 11]
The positive integers should ideally be:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
Numbers missing from the array are:
1, 5, 6, 8, 9, 10, ...
Our goal is to find the kth number in this missing sequence.
Naive Approach
A straightforward solution would be:
Start from 1.
Check whether each number exists in the array.
Count missing numbers.
Stop when the kth missing number is found.
Complexity
O(n + k)
This becomes inefficient when k is very large.
Optimized Approach: Binary Search
Since the array is already sorted, we can use binary search.
The key is to determine how many numbers are missing before a particular index.
Step 1: Count Missing Numbers Before an Index
At index i, if no numbers were missing, we would expect:
arr[i] = i + 1
The actual value is larger because some numbers are missing.
Therefore:
missing(i) = arr[i] - (i + 1)
This gives the number of missing positive integers before arr[i].
Example
arr = [2, 3, 4, 7, 11]
At index 0:
missing(0) = 2 - 1 = 1
At index 3:
missing(3) = 7 - 4 = 3
At index 4:
missing(4) = 11 - 5 = 6
Why Binary Search Works
We want to find the first position where:
missing(i) ≥ k
Why?
Because the kth missing number must occur before that position.
This creates a monotonic property:
That makes binary search applicable.
Binary Search Strategy
Maintain two pointers:
left = 0
right = n - 1
For each midpoint:
mid = left + (right - left) / 2
Compute:
missing = arr[mid] - (mid + 1)
Case 1: Missing Numbers Are Less Than k
If:
missing < k
the answer lies further right.
left = mid + 1
Case 2: Missing Numbers Are Greater Than or Equal to k
If:
missing ≥ k
the answer lies to the left.
right = mid - 1
Computing the Final Answer
After binary search completes:
left
represents the first position where:
missing(left) ≥ k
The kth missing number is:
left + k
Why Does left + k Work?
By the time we reach index left:
Combining both gives:
kth missing = left + k
Example Walkthrough
Input
arr = [2, 3, 4, 7, 11]
k = 5
Missing Counts
missing(0) = 1
missing(1) = 1
missing(2) = 1
missing(3) = 3
missing(4) = 6
We need:
missing(i) ≥ 5
The first such index is:
left = 4
Therefore:
kth missing = left + k
= 4 + 5
= 9
Answer
9
Java Implementation
class Solution {
public int kthMissing(int[] arr, int k) {
int n = arr.length;
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int missing = arr[mid] - (mid + 1);
if (missing < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// left is the position where missing(left) >= k
return left + k;
}
}
Complexity Analysis
Time Complexity
Binary search processes the array in:
O(log n)
Space Complexity
Only a few variables are used:
O(1)
Pattern Recognition
This problem belongs to the family of:
A common clue is when:
In such cases, binary search is often the optimal solution.
Key Takeaway
The crucial observation is that the number of missing elements before index i can be calculated as:
arr[i] - (i + 1)
This creates a monotonic sequence that allows binary search. Instead of generating missing numbers one by one, we locate the first index where the missing count reaches k and directly compute the answer in logarithmic time.
Summary
To find the kth missing positive number efficiently, calculate how many numbers are missing before each array index using arr[i] - (i + 1). Since this count increases monotonically, binary search can be used to find the first index where the missing count becomes at least k. The final answer is then computed as left + k, resulting in an optimal O(log n) time and O(1) space solution.