Table of contents
Problem
Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Return thekthpositive integer that is missing from this array. (link)
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.
Example 2:
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...].
The 2nd missing positive integer is 6.
Constraints:
1 <= arr.length <= 10001 <= arr[i] <= 10001 <= k <= 1000arr[i] < arr[j]for1 <= i < j <= arr.length
Follow up:
Could you solve this problem in less than O(n) complexity?
Solution
Brute force Approach
We have a missing element, and if we add the count of the elements which were already present to 'k', then we will identify the missing element, and that will be our answer.
Time - O(n)
Space - O(1)
public int findKthPositive(int[] arr, int k) {
for(int i=0; i<arr.length; i++){
if(k<arr[i]) return k;
k+=1;
}
return k;
}
Optimal Approach - Binary Search
Apply binary search. We check from the current index how many elements are missed so far. If the elements missed so far are fewer than 'k', then we move towards the right; otherwise, we move towards the left. If it is outside the given array range, then the answer is straightaway 'low + k'.
Example:
If the start element is 6 and 'k' is 4, then the missing element is 4.
low + k = 0 + 4 = 4
If the end element is 44 (array length is 44) and 'k' is 50, then the missing element is:
low + k = 45 + 50 = 95.
Because in binary search, the search goes to the right, and hence the low pointer goes out of range first
Time - O(logn)
Space - O(1)
public int findKthPositive(int[] arr, int k) {
int low = 0;
int high = arr.length-1;
while(low<=high){
int mid = (low+high)/2;
if(arr[mid]-(mid+1)<k){
low = mid + 1;
}
else{
high = mid -1;
}
}
return low + k;
}