Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the k<sup>th</sup> 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 5<sup>th</sup>&nbsp;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 2<sup>nd</sup> missing positive integer is 6.

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

## Finding the Kth Missing Positive Integer

This problem asks us to find the k-th positive integer that is missing from a strictly increasing array of positive integers.

### 1. Brute Force Solution

The most straightforward approach is to iterate through positive integers, checking if each integer is present in the array. We maintain a count of missing integers and return the integer when the count reaches `k`.

```python
def findKthPositive_brute_force(arr, k):
    missing_count = 0
    num = 1
    i = 0
    
    while missing_count < k:
        if i < len(arr) and arr[i] == num:
            num += 1
            i += 1
        else:
            missing_count += 1
            if missing_count == k:
                return num
            num += 1

2. Optimal Solution: Binary Search

Since the array is sorted, we can use binary search to efficiently find the k-th missing positive integer. The idea is to find the index idx in the array such that arr[idx] - (idx + 1) is the largest value less than k. This indicates that the k-th missing number lies between arr[idx] and arr[idx+1] or after the last element of the array if idx is the last index.

def findKthPositive(arr, k):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        missing = arr[mid] - (mid + 1)
        
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
            
    # k-th missing number is k + right + 1 (if right is not -1)
    # or k (if right is -1, which means all numbers in arr are greater than k)
    return k + right + 1

3. Big(O) Runtime Analysis

• Brute Force: O(N + K), where N is the length of the array and K is the k-th missing number.
• Binary Search: O(log N), where N is the length of the array. We perform a binary search to find the index, making it more efficient.

4. Big(O) Space Usage Analysis

• Both solutions have O(1) space complexity as they use a constant amount of extra space.

5. Edge Cases

• Empty Array: If the input array is empty, the k-th missing positive integer is simply k.
• k is smaller than the first missing integer: If k is smaller than the first missing integer, the result is k.
• k is larger than all missing integers before the last element: Binary search handles this case by moving left to len(arr). Then the result would be k + right + 1 = k + len(arr).

Here is the code with all the edge cases covered:

def findKthPositive(arr, k):
    if not arr:
        return k

    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        missing = arr[mid] - (mid + 1)

        if missing < k:
            left = mid + 1
        else:
            right = mid - 1

    return k + right + 1