LeetCode 1060: Missing Element in Sorted Array

Problem Restatement

We are given a sorted integer array nums with no duplicates and an integer k.

We need to return the k-th missing number starting from the leftmost element.

The official constraints state that 1 <= nums.length <= 5 * 10^4 and 1 <= k <= 10^8.

Input and Output

Function shape:

def missingElement(nums: list[int], k: int) -> int:
    ...

Examples

Example 1:

nums = [4, 7, 9, 10]
k = 1

Missing numbers starting from 4: 5, 6, 8, …

First missing: 5.

Answer:

5

Example 2:

nums = [4, 7, 9, 10]
k = 3

Missing: 5, 6, 8. Third missing: 8.

Answer:

8

Key Insight

The number of integers missing before index i is nums[i] - nums[0] - i.

Use binary search to find the largest index i where missing(i) < k. The answer is after nums[i].

Algorithm

1. Define missing(i) = nums[i] - nums[0] - i.
2. Binary search for the largest i where missing(i) < k.
3. Return nums[i] + (k - missing(i)).

Edge Cases

• Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
• Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
• When the target is absent, the loop should still terminate and return the problem-specific failure value.

Complexity

Common Pitfalls

• Do not mix inclusive and half-open bounds inside the same loop.
• Make sure each branch strictly reduces the search interval.

Implementation

class Solution:
    def missingElement(self, nums: list[int], k: int) -> int:
        def missing(i):
            return nums[i] - nums[0] - i

        n = len(nums)
        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))

Testing

def run_tests():
    s = Solution()

    assert s.missingElement([4,7,9,10], 1) == 5
    assert s.missingElement([4,7,9,10], 3) == 8
    assert s.missingElement([1,2,4], 3) == 6

    print("all tests passed")

run_tests()