Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1060 with 12 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1060 # by problem number
lcpy gen -s missing_element_in_sorted_array # by problem name
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.
Input: nums = [4,7,9,10], k = 3
Output: 8
Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8.
Input: nums = [1,2,4], k = 3
Output: 6
Explanation: The missing numbers are [3,5,6,7,...], hence the third missing number is 6.
O(log(n))) solution?
class Solution:
# Time: O(log n)
# Space: O(1)
def missing_element(self, nums: list[int], k: int) -> int:
def missing(i: int) -> int:
return nums[i] - nums[0] - i
n = len(nums)
if k > missing(n - 1):
return nums[n - 1] + k - missing(n - 1)
left, right = 0, n - 1
while left < right:
mid = (left + right) >> 1
if missing(mid) >= k:
right = mid
else:
left = mid + 1
return nums[left - 1] + k - missing(left - 1)
| Time | Space |
|---|---|
| O(log n) | O(1) |