Intermediate Level
Implement the kthMissingPositiveNumber method that returns the kth missing positive integer from a sorted array.
You are given a strictly increasing sorted array of positive integers and a value k. Return the kth positive integer that is missing from the array.
For example, in [2,3,4,7,11], the missing positive integers start as 1,5,6,8,9,....
Example 1
Input
nums (int[]) =
[2,3,4,7,11]size (int) =
5k (int) =
5Returns (int)
9Example 2
Input
nums (int[]) =
[1,2,3,4]size (int) =
4k (int) =
2Returns (int)
6Example 3
Input
nums (int[]) =
[5,6]size (int) =
2k (int) =
1Returns (int)
1Use binary search on how many numbers are missing before each index.
At index i, the number of missing positive integers before nums[i] is nums[i] - (i + 1). Find the first index where the missing count is at least k. The answer can then be calculated from the search boundary.
This avoids scanning every missing number one by one.
Pseudocode:
function kthMissingPositiveNumber(nums, size, k):
left = 0
right = size
while left < right:
mid = (left + right) / 2
missing = nums[mid] - (mid + 1)
if missing < k:
left = mid + 1
else:
right = mid
return left + kReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run