1539. Kth Missing Positive Number

Thinking process:

edge cases (1) left boundary arr[0] > k (2) right boundary missing_count(right) < k
now result is limited to between left and right
there could be more than 1 index with missing_count() == k, to ensure the first one is included within [left, right], when missing_count(mid) == k we should let right = mid instead of left = mid. Imagine missing_count(mid) is the not first index that equals to k, then left = mid will exclude the first one
```
if missing_count(mid) >= k: 
           right = mid
       else:
           left = mid
```

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        def missing_count(index):
            return arr[index] - 1 - index

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

        if arr[0] > k:
            return k

        # k-th missing number is beyond the last element
        if missing_count(right) < k:
            return arr[right] + k - missing_count(right)

        while left + 1 < right:
            mid = left + (right-left) // 2

            # >= ensures we include the case where left of nums[mid] is exactly where we find k missing elements
            if missing_count(mid) >= k: 
                right = mid
            else:
                left = mid
        
        # left and right are adjacent (left + 1 == right)
        return arr[left] + k - missing_count(left)

using bisect

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        def missing_count(index):
            return arr[index] - 1 - index
        
        if arr[0] > k:
            return k

        missing_counts = [missing_count(i) for i in range(len(arr))]
        
        # Use bisect_left to find the first index where the missing count is >= k
        idx = bisect_left(missing_counts, k)
        
        # If k-th missing number is beyond the last element
        if idx == len(arr):
            return arr[-1] + k - missing_counts[-1]
        
        # Otherwise, calculate the k-th missing number
        return arr[idx - 1] + k - missing_counts[idx - 1]

1539. Kth Missing Positive Number - cocoder39/coco39_LC GitHub Wiki