Understanding the Problem
We are given a sorted array of distinct positive integers, and we are asked to find the kth missing positive number.
To put it simply, we need to simulate counting from 1 upwards and identify which positive numbers are not present in the array. The kth
number among those missing is our answer.
For example, consider the array [2, 3, 4, 7, 11]
and k = 5
. The missing numbers are [1, 5, 6, 8, 9, 10]
, so the 5th missing number is 9
.
Step-by-Step Solution with Example
step 1: Identify expected and actual values
At index i
, the expected value is i + 1
if all numbers were present. But the actual value is arr[i]
. So the total number of missing values up to index i
is:
missingCount = arr[i] - (i + 1)
step 2: Iterate or use binary search
We traverse the array and for each index, calculate how many numbers are missing so far. If missingCount < k
, we move forward. When we find the first index where missingCount ≥ k
, we know the missing number lies before arr[i]
.
step 3: Use the previous value and compute the answer
If missingCount
becomes ≥ k
at index i
, we use:
arr[i - 1] + (k - missingBeforePrevious)
This finds how many numbers we still need to add after the previous element to reach the kth missing.
step 4: Handle the case when all missing numbers are after the array ends
If the entire array is not missing enough values, the missing numbers are beyond the last element. Then the answer is:
arr[n - 1] + (k - totalMissing)
Example: arr = [2, 3, 4, 7, 11], k = 5
Index Value MissingCount
0 2 1 (1 is missing)
1 3 1 (no new missing)
2 4 1 (no new missing)
3 7 3 (5 and 6 are missing)
4 11 6 (8, 9, 10 are also missing)
At index 4, missing count is 6 ≥ 5, so kth missing lies before 11.
Previous value = 7, previous missing = 3
Still need 5 - 3 = 2 more steps → 7 + 2 = 9
Answer: 9
Edge Cases
- Array starts after 1: If the array starts from a number > 1, initial values are missing (e.g., [4, 5] → missing = [1, 2, 3])
- Array has no gaps: If array is like [1, 2, 3], the missing values begin after the end → kth missing = last + k
- Empty array: If the array is empty, kth missing = k itself
- k is small: Often the missing number lies before any actual gap. Be sure to check the first element.
Finally
This problem teaches us how to track missing values efficiently using either a loop or binary search. The key insight is to compare the expected count of numbers versus the actual values in the array. With this, we can find the exact position of the kth missing number without simulating the entire sequence.
Binary search gives us an efficient solution for large arrays with O(log n) time complexity, while linear scan also works fine for small inputs.
Comments
Loading comments...