Missing Element in Sorted Array — Binary Search on Missing Count [LC 1060, Google]

Problem Statement#

Given a sorted integer array nums with no duplicates and a positive integer k, return the k-th missing number starting from the leftmost element.

Constraints:

• 1 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^7
• nums is strictly increasing
• 1 <= k <= 10^8

Input:  nums = [4,7,9,10], k = 1
Output: 5

Input:  nums = [4,7,9,10], k = 3
Output: 8

Why This Problem Matters#

LC 1060 is a Google interview problem that tests the ability to use binary search on a derived function rather than on the array values directly. The missing-count function missing(i) = nums[i] - nums[0] - i is monotone non-decreasing, which makes it amenable to binary search.

The challenge is two-fold: recognise that the missing-count function is the searchable quantity, and then correctly reconstruct the actual missing number from the boundary index. This reconstruction step is where most candidates make errors.

The Core Insight#

At index i, the number of integers in the range [nums[0], nums[i]] that are missing from nums is:

• Total integers in the range: nums[i] - nums[0] + 1
• Integers present (indices 0 through i): i + 1
• Missing: nums[i] - nums[0] + 1 - (i + 1) = nums[i] - nums[0] - i

This function is monotone non-decreasing. Binary search for the first index where missing(i) >= k. The answer lies just after nums[lo - 1].

If k > missing(n-1) (more missing numbers asked than exist within the array range), the answer is beyond the array: nums[-1] + (k - missing(n-1)).

Visual Dry Run#

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

Missing counts: missing(0) = 0, missing(1) = 2, missing(2) = 3, missing(3) = 3

lo = 2. Answer = nums[lo-1] + k - missing(lo-1) = nums[1] + 3 - 2 = 7 + 1 = 8. Correct.

Solution (Optimal)#

class Solution:
    def missingElement(self, nums: list[int], k: int) -> int:
        n = len(nums)
 
        def missing(i: int) -> int:
            return nums[i] - nums[0] - i
 
        # Check if answer is beyond the array
        if k > missing(n - 1):
            return nums[-1] + k - missing(n - 1)
 
        # Binary search: find first index where missing count >= k
        lo, hi = 0, n - 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if missing(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
 
        # lo is the first index with missing count >= k
        # nums[lo - 1] has missing count < k
        # the answer is k - missing(lo-1) steps after nums[lo-1]
        return nums[lo - 1] + k - missing(lo - 1)

var missingElement = function(nums, k) {
    const n = nums.length;
 
    function missing(i) {
        return nums[i] - nums[0] - i;
    }
 
    // If answer is beyond the array range
    if (k > missing(n - 1)) {
        return nums[n - 1] + k - missing(n - 1);
    }
 
    let lo = 0, hi = n - 1;
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (missing(mid) >= k) hi = mid;
        else lo = mid + 1;
    }
 
    // Reconstruct the missing number
    return nums[lo - 1] + k - missing(lo - 1);
};

Time: O(log n) — single binary search over the array indices Space: O(1) — only pointer and counter variables

Common Mistakes#

• Forgetting the out-of-range case: when k exceeds the total missing count within the array, the answer is beyond nums[-1].
• Off-by-one in reconstruction: using lo instead of lo - 1 for the recovery formula gives a wrong answer.
• Confusing the missing-count function with the value function — you are searching on counts, not on nums values.
• Not handling lo = 0 after the binary search — if the first element already has missing(0) >= k, lo - 1 underflows; but missing(0) = 0 < k always (since k >= 1), so lo is always >= 1 after the search.

Interview Tips#

• Define missing(i) as a helper to keep the code readable.
• Draw out the missing counts for the example input before coding — it makes the reconstruction formula obvious.
• State the out-of-bounds case before starting the binary search so the interviewer sees your edge-case awareness.
• The reconstruction nums[lo-1] + k - missing(lo-1) says: "start at the last safe number, then take the remaining missing steps."

Follow-up Questions#

• What if the array has duplicates? Deduplicate first, then apply the same algorithm.
• What if k is very large (up to 10^8)? No change — the algorithm handles it in the out-of-bounds branch.
• Linear scan version: Walk through the array, decrementing k for each gap. O(n) — correct but not the expected solution.
• LC 268 (Missing Number): Simpler version — one number missing from 0..n. Use XOR or sum formula.
• How would you handle a stream of queries? Pre-compute missing(i) for all i in O(n) and binary search per query in O(log n) per query.

Key Takeaways#

• LC 1060 uses binary search on the derived missing-count function missing(i) = nums[i] - nums[0] - i, which is monotone non-decreasing.
• Find the first index where missing(i) >= k using left-boundary binary search (hi = mid on success).
• The reconstruction formula is: nums[lo-1] + k - missing(lo-1) — start after the last safe element and count remaining gaps.
• Handle the out-of-bounds case first: when k > missing(n-1), the answer lies beyond the array end.
• The missing-count function is the key insight — recognising that a derived, monotone function can be binary-searched is a high-signal skill in interviews.
• Google asks this problem specifically to test creative reframing: the array is sorted by value but you binary search by count.
• This technique generalises to any problem where a derived monotone function of the array index is the searchable quantity.