Missing Element in Sorted Array

How it works

Instead of scanning linearly, we can use binary search to find the position where the k-th missing number falls. The key observation is that for any index i, the count of missing numbers up to that point equals nums[i] - nums[0] - i. This formula works because in a complete sequence starting from nums[0], we would expect nums[0] + i at index i. The difference tells us how many numbers were skipped. Since this count is monotonically increasing, binary search applies naturally.

Steps

1. Initialize left = 0 and right = n - 1.
2. While left < right:
   • Calculate mid using upper mid to avoid infinite loops.
   • Compute the number of missing elements up to index mid: missing = nums[mid] - nums[0] - mid.
   • If missing < k, the k-th missing number is to the right, so set left = mid.
   • Otherwise, set right = mid - 1.
3. After the loop, left points to the largest index where the count of missing numbers is less than k.
4. Return nums[0] + k + left.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1) constant space

Where n is the length of the input array nums.

Things to watch for

Miscounting Missing Elements

The formula for counting missing elements up to index i is nums[i] - nums[0] - i. Using nums[i] - i without subtracting nums[0] gives incorrect counts when the array does not start at 0 or 1.

Handling the Missing Element Beyond the Array

When k exceeds the total count of missing elements within the array, the answer lies beyond the last element. Failing to account for this case and only searching within array bounds leads to incorrect results or out-of-bounds errors.

Binary Search Boundary Errors

Using the wrong mid calculation or boundary updates can cause infinite loops or skip valid positions. The upper-mid formula mid = right - (right - left) / 2 is used here to avoid getting stuck; using standard lower-mid without proper boundary handling leads to incorrect convergence.

from typing import List

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        n = len(nums)
        left, right = 0, n - 1

        while left < right:
            mid = right - (right - left) // 2
            if (nums[mid] - nums[0]) - mid < k:
                left = mid
            else:
                right = mid - 1

        return nums[0] + k + left

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0, right = n - 1;

        while (left < right) {
            int mid = right - (right - left) / 2;
            if (nums[mid] - nums[0] - mid < k) {
                left = mid;
            } else{
                right = mid - 1;
            }
        }

        return nums[0] + k + left;
    }
};