-
Notifications
You must be signed in to change notification settings - Fork 0
LC 1060 [M] Missing Element in Sorted Array
Code with Senpai edited this page Sep 27, 2022
·
6 revisions
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
footer