1060. Missing Element in Sorted Array

recognize this is a binary search problem
2 cases: 1. kth missing is beyond the array 2. kth missing is within the array
for case 2, binary search is applied and the final range is [left: right+1] and right == left + 1. so we can use left to infer kth missing

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        # calculate missing elements up to the given index
        def missing_count(index):
            return nums[index] - nums[0] - index

        left, right = 0, len(nums)-1
        # k-th missing number is beyond the last element
        if missing_count(right) < k:
            return nums[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 nums[left] + k - missing_count(left)

bisect

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
       # Calculate missing elements up to the given index
        def missing_count(index):
            return nums[index] - nums[0] - index

        # Calculate missing counts array
        missing_counts = [missing_count(i) for i in range(len(nums))]

        # If k-th missing number is beyond the last element
        if missing_counts[-1] < k:
            return nums[-1] + k - missing_counts[-1]

        # Use bisect_left to find the first index where the missing count is >= k
        idx = bisect_left(missing_counts, k)

        # Calculate the k-th missing number
        return nums[idx - 1] + k - missing_counts[idx - 1]

1060. Missing Element in Sorted Array - cocoder39/coco39_LC GitHub Wiki