LC 1060 [M] Missing Element in Sorted Array - ALawliet/algorithms GitHub Wiki

Given an integer array nums which is sorted in ascending order and all of its elements are unique and given also an integer k, return the kth missing number starting from the leftmost number of the array.

Input: nums = [4,7,9,10], k = 1
Output: 5
Explanation: The first missing number is 5.

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        # how many numbers missing until i        
        missing_at = [(nums[i] - nums[0] - i) for i in range(len(nums))]
        print(missing_at)
        
        n = len(nums)
        
        # k > last missing count so the missing numbers are created at the end
        if k > missing_at[-1]:
            return nums[-1] + k - missing_at[-1] # -1
        
        # k <= missing_at[-1] # the kth missing number is before the last element
        else:
            # leftmost binary search
            lm = bisect_left(missing_at, k)
            # similar to return above but based on l (-1 because k is not 0-indexed)
            return nums[lm-1] + k - missing_at[lm-1] # l-1

l = bisect_left(missing, k)

l, r = 0, n - 1
while l < r:
    m = (l + r) // 2
            
    if not k <= missing_at[m]:
        l = m + 1
    else:
        r = m