1539. Kth Missing Positive Number(Solution || Leetcode easy || Java)

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.

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 <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr[i] < arr[j] for 1 <= i < j <= arr.length

Follow up:

Could you solve this problem in less than O(n) complexity?

SOLUTION:

Brute force

class Solution {
public int findKthPositive(int[] arr, int k) {
int count = 0;//A counter variable for counting missing numbers
int n = 1;//Its value will increase by 1 in every loop and it will get checked which number is missing
int index = 0;//if number found in array index will increase by 1 else count will increase by 1

while(count < k){
if(index < arr.length && arr[index] == n){
index += 1;
}else{
count++;
}
n++;
}

return n-1;//In the last loop our answer will increase by 1 so we minus 1 from it
}
}

TIME COMPLEXITY :- O(n)

SPACE COMPLEXITY :- O(1)

SOLUTION 2:-

class Solution {
public int findKthPositive(int[] arr, int k) {
int start = 0;//determining range for binary search
int end = arr.length — 1;

int closestNum = 0;//the number just after which we are going to find our kth missing is our closest num

while(start <= end){//applying binary search
int mid = start + (end — start)/2;

//by subtracting index+1 from the element present at that index we will get to know how many numbers are missing before that element.

if(arr[mid] — (mid+1) < k){
closestNum = mid + 1;
start = mid + 1;
}else{
end = mid — 1;
}
}

return k + closestNum;
}
}

TIME COMPLEXITY:- O(log(n))

SPACE COMPLEXITY:- O(1)

Thank you for reading. If you have any queries then, please let me know in the comment section, I will surely responsive toward that.