⚡Flashcard Drill➔
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

  1. Define missing(i) = nums[i] - nums[0] - i, the number of missing values strictly before index i.
  2. If k > missing(n-1), the answer lies beyond the array: nums[-1] + (k - missing(n-1)).
  3. Otherwise binary search for the smallest i with missing(i) >= k.
  4. 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 k exceeds the missing count inside the array, the answer is past nums[-1].
  • Defining missing(i) with the wrong offset: it is nums[i] - nums[0] - i, because i values are already present.
  • Returning nums[lo]: the answer is derived by counting forward from nums[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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems