NeetCode #268LC-1060MediumBinary SearchNC Algo100
← Back to All Problems#268 · #1060 · Missing Element in Sorted Array(有序数组中的缺失元素)
📌 Problem Statement & Constraints
Given an integer array
nums sorted ascending with distinct values and an integer k, return the k-th missing number starting from nums[0]. Constraints: 1 <= nums.length <= 5 * 10^4, 1 <= k <= 10^8, 1 <= nums[i] <= 10^7.💡 Core Algorithmic Approaches
- Define
missing(i) = nums[i] - nums[0] - i, the number of missing values strictly before indexi. - If
k > missing(n-1), the answer lies beyond the array:nums[-1] + (k - missing(n-1)). - Otherwise binary search for the smallest
iwithmissing(i) >= k. - Then the answer is
nums[i-1] + (k - missing(i-1)), i.e. count forward from the previous element.
💻 Benchmark Python3 Implementation
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
n = len(nums)
def missing(i: int) -> int:
# how many values in [nums[0], nums[i]] are absent from nums
return nums[i] - nums[0] - i
if k > missing(n - 1):
return nums[-1] + (k - missing(n - 1))
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if missing(mid) < k:
lo = mid + 1
else:
hi = mid
return nums[lo - 1] + (k - missing(lo - 1))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log n): one binary search after the O(1) boundary check.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the out-of-range case: when
kexceeds the missing count inside the array, the answer is pastnums[-1]. - Defining
missing(i)with the wrong offset: it isnums[i] - nums[0] - i, becauseivalues are already present. - Returning
nums[lo]: the answer is derived by counting forward fromnums[lo-1]. - Assuming duplicates: the problem guarantees distinct values; with duplicates the missing-count formula changes.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.