Kth Missing Positive Number
Leetcode Daily Challenge (6th March, 2023)
Problem Statement:-
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.
Link: leetcode.com/problems/kth-missing-positive-..
Problem Explanation with examples:-
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.
Example 3
Input: arr = [1,2,3,4], k = 3
Output: 7
Explanation: The missing positive integers are [5,6,7,...]. The 3rd missing positive integer is 7.
Constraints
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length
Intuition:-
Here our concerns are the ones that are not in the array but appear in the sequence of natural numbers. What could be our limit to checking for missing numbers? The last element of the given array + k. Why?
Because if the given array is a continuous sequence of natural numbers starting from 1, then the missing numbers will start after the last element of the array. So, we can check for the missing numbers till the last element of the array + k.
One might think of storing the missing numbers in a list or ArrayList and then returning the kth element of the list. But, that would be a waste of space. We can just keep a count of the missing numbers and return the kth missing number when we reach count k.
So putting it all together we have to iterate through the natural numbers from 1, and whenever we encounter a number that is not in the given array, we increment the count of missing numbers. When the count reaches k, we return the number that we are currently at.
Solution:-
Initialize a count variable c to 0 for keeping track of the index of the array where we are currently at - in simple words it keeps track of the elements present in the array and increments when we encounter the same element in the natural numbers sequence.
Initialize a variable x to 0 for keeping track of the missing numbers and increments when we encounter a number that is not in the given array.
c = 0
x = 0
- then we iterate through the natural numbers from 1 to the last element of the array + k.
for i in range(1,arr[len(arr)-1]+k+1):
If c is greater than or equal to the length of the array or the number that we are currently at is not equal to the element at index c of the array, we increment the count of missing numbers x.
Also we check if x is equal to k, if yes, we return the number that we are currently at.
If the number that we are currently at is equal to the element at index c of the array, we increment the count c.
if c >= len(arr) or i != arr[c]:
x += 1
if x == k:
return i
else:
c += 1
- If we reach the end of the loop, we return -1. (Possibly we won't reach here)
- A binary search solution is also possible, try it out.
Code:-
JAVA Solution
class Solution {
public int findKthPositive(int[] arr, int k) {
int c = 0;
int x = 0;
for (int i = 1; i <= arr[arr.length - 1] + k; i++) {
if (c >= arr.length || i != arr[c]) {
x++;
if (x == k) {
return i;
}
} else {
c++;
}
}
return -1;
}
}
Python Solution
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
c = 0
x = 0
for i in range(1,arr[len(arr)-1]+k+1):
if c >= len(arr) or i != arr[c]:
x += 1
if x == k:
return i
else:
c += 1
return -1
Complexity Analysis:-
TIME:-
Time complexity is O(n+k) as we iterate through the natural numbers from 1 to the last element of the array + k.
SPACE:-
Space complexity is O(1), as we don't use any extra space.