Missing Element in Sorted Array — Binary Search on Missing Count

Problem 323 · Missing Element in Sorted Array

Difficulty: Medium · Pattern: BS on Missing Count

The kth missing number starting from the first element.

Intuition

At index i, missing count = nums[i] - nums[0] - i. Binary search for the first index where missing count >= k.

Solutions

# Python
def missingElement(nums, k):
    n = len(nums)
    # total missing up to end
    if k > nums[-1]-nums[0]-n+1:
        return nums[-1] + k - (nums[-1]-nums[0]-n+1)
    lo, hi = 0, n-1
    while lo < hi:
        mid = (lo+hi)//2
        missing_at_mid = nums[mid]-nums[0]-mid
        if missing_at_mid < k: lo = mid+1
        else: hi = mid
    # lo-1 is the last index with fewer than k missing
    return nums[lo-1] + k - (nums[lo-1]-nums[0]-(lo-1))

// Java
public int missingElement(int[] nums, int k) {
    int n=nums.length;
    if (k>nums[n-1]-nums[0]-n+1) return nums[n-1]+k-(nums[n-1]-nums[0]-n+1);
    int lo=0, hi=n-1;
    while (lo<hi) {
        int mid=lo+(hi-lo)/2;
        if (nums[mid]-nums[0]-mid<k) lo=mid+1; else hi=mid;
    }
    return nums[lo-1]+k-(nums[lo-1]-nums[0]-(lo-1));
}

Complexity

Time: O(log n)
Space: O(1)