1539. Kth Missing Positive Number

To find the kth missing positive number in a sorted array, we can use the fact that it’s sorted to find the number in $O(\log n)$ time.

Note that if say arr[i] = 5 where i is 3, then we know that arr[i] - i - 1 items are missing. We can then find the index where arr[i] - i > k, add k to i, and find the missing number.

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        lo, hi = 0, len(arr)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] - mid > k: 
                hi = mid
            else: 
                lo = mid + 1
        return lo + k