Given a sorted array of distinct positive integers arr[], we need to find the kth positive number that is missing from arr[].
Examples :
Input: arr[] = [2, 3, 4, 7, 11], k = 5
Output: 9 Explanation: Missing are 1, 5, 6, 8, 9, 10… and 5th missing number is 9.
Input: arr[] = [1, 2, 3], k = 2 Output: 5 Explanation: Missing are 4, 5, 6… and 2nd missing number is 5.
Input: arr[] = [3, 5, 9, 10, 11, 12], k = 2 Output: 2 Explanation: Missing are 1, 2, 4, 6… and 2nd missing number is 2.
Constraints:
1 <= arr.size() <= 105
1 <= k <= 105
1 <= arr[i]<= 106
Approach 01:
-
C++
-
Python
#include <vector> #include <unordered_set> using namespace std; class Solution { public: int kthMissing(vector<int>& arr, int k) { unordered_set<int> elementCount(arr.begin(), arr.end()); int maxRange = arr.size() + k + 1; int missingNumber = -1; for (int currentNumber = 1; currentNumber < maxRange; ++currentNumber) { if (elementCount.find(currentNumber) != elementCount.end()) { continue; } if (k > 0) { missingNumber = currentNumber; --k; } if (k == 0) { return missingNumber; } } return missingNumber; } };
import collections class Solution: def kthMissing(self, arr, k): elementCount = collections.Counter(arr) maxRange = len(arr) + k + 1 missingNumber = -1 for currentNumber in range(1, maxRange): if elementCount[currentNumber] == 1: continue if k > 0: missingNumber = currentNumber k -= 1 if k == 0: return missingNumber return missingNumber
Time Complexity
- Building the Unordered Set:
- The unordered set
elementCount
is built from the input arrayarr
, which has \(n\) elements. - Inserting each element into the unordered set takes \(O(1)\) on average, resulting in a total of \(O(n)\) time for this step.
- The unordered set
- Iterating Through the Range:
- The range of numbers checked is up to \(\text{maxRange} = n + k + 1\), which is approximately \(O(n + k)\).
- For each number, a lookup in the unordered set
elementCount
is performed, which takes \(O(1)\) on average. - The total time complexity for this step is \(O(n + k)\).
- Overall Time Complexity:
The total time complexity is \(O(n + k)\), where \(n\) is the size of the input array and \(k\) is the number of missing elements to find.
Space Complexity
- Input Storage:
- The input array
arr
requires \(O(n)\) space.
- The input array
- Auxiliary Data Structures:
- The unordered set
elementCount
stores all elements of the input array, requiring \(O(n)\) space. - A few integer variables such as
maxRange
,missingNumber
, and loop counters require \(O(1)\) space.
- The unordered set
- Overall Space Complexity:
The total space complexity is \(O(n)\), dominated by the unordered set.