1060. Missing Element in Sorted Array(Binary Search) 20.9.12 Medium

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

 

Example 1:

Input: A = [4,7,9,10], K = 1
Output: 5
Explanation: 
The first missing number is 5.
Example 2:

Input: A = [4,7,9,10], K = 3
Output: 8
Explanation: 
The missing numbers are [5,6,8,...], hence the third missing number is 8.
Example 3:

Input: A = [1,2,4], K = 3
Output: 6
Explanation: 
The missing numbers are [3,5,6,7,...], hence the third missing number is 6.
 

Note:

1 <= A.length <= 50000
1 <= A[i] <= 1e7
1 <= K <= 1e8


Solution no.1: Linear scan O(N) T
class Solution(object):
    def missingElement(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        for i in range(1, len(nums)):
            curr_diff = nums[i] - nums[i - 1] - 1
            if curr_diff >= k:
                return nums[i - 1] + k
            k -= curr_diff
        
        if k != 0:
            return nums[-1] + k
            
            
Solution no.2: Binary Search O(logN) T
class Solution(object):
    def missingElement(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = (left + right) / 2
            curr_gap = self.find_empty_count(nums, left, mid)
            if curr_gap >= k:
                right = mid
            else:
                left = mid
                k -= curr_gap
        
        if nums[left] + k < nums[right]:
            return nums[left] + k
        k -= nums[right] - nums[left] - 1
        return nums[right] + k
                
            
            
            
    def find_empty_count(self, nums, start, end):
        return nums[end] - nums[start] - 1 - (end - start - 1)