Kth Missing Positive Number in a Sorted Array

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() <= 10⁵
1 <= k <= 10⁵
1 <= arr[i]<= 10⁶

Approach 01:

#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 array arr, 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.
• 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.
• 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.
• Overall Space Complexity:

  The total space complexity is \(O(n)\), dominated by the unordered set.