Hey Guys! It's day 78 and we are going to do another binary Search question. This problem is quite easy so I won't be going in depth about problem breakdown.
Question: Finding Kth Missing Positive Integer
Problem Description
Given an array arr
of positive integers sorted in a strictly increasing order, and an integer k
.
Return the kth
positive integer that is missing from this array.
Example 1:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.
Approach Overview
The problem can be solved efficiently using a binary search approach. The idea is to perform a binary search on the array to find the position where the kth missing positive integer should be located.
The approach involves the following steps:
Initialize two pointers
left
andright
representing the search range.left
starts from 0 andright
starts fromn - 1
, where n is the size of the array.Perform a binary search loop while
left
is less than or equal toright
.Calculate the midpoint
mid
of the search range.Calculate the number of missing positive integers up to the
mid
index usingmissingCount = arr[mid] - (mid + 1)
.Compare the
missingCount
with the givenk
:
If
missingCount
is less thank
, it means that the kth missing positive integer is to the right of themid
index. In this case, updateleft = mid + 1
.If
missingCount
is greater than or equal tok
, it means that the kth missing positive integer is to the left of or at themid
index. In this case, updateright = mid - 1
.
- After the binary search loop, the kth missing positive integer can be found at
k + right + 1
.
Code:
class Solution {
public:
int findKthPositive(vector<int>& arr, int k) {
int n = arr.size();
int left = 0, right = n - 1; // Initialize search range
while (left <= right) { // Binary search loop
int mid = (left + right) / 2; // Calculate midpoint
int missingCount = arr[mid] - (mid + 1); // Calculate missing count
if (missingCount < k) {
// If missing count is less than k, move search to the right
left = mid + 1;
} else {
// If missing count is greater than or equal to k, move search to the left
right = mid - 1;
}
}
// The kth missing integer is found at k + right + 1
return k + right + 1;
}
};
Complexity Analysis:
Complexity | Notation | Explanation |
---|---|---|
Time | O(log N) | The binary search performs a logarithmic number of iterations. |
Space | O(1) | The algorithm uses a constant amount of extra space. |
Top comments (0)