Missing Element in Sorted Array

medium binary search sorted array math

Problem

Given an integer array nums which is sorted in ascending order and all of its elements are distinct, and given an integer k, return the kth missing number starting from the leftmost number nums[0].

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

Output8

The missing numbers in order are 5, 6, 8, 11, 12, … so the 3rd missing number is 8.

nums (sorted, comma-separated)

def missing_element(nums, k):
    n = len(nums)
    def missing(i):
        return nums[i] - nums[0] - i
    if k > missing(n - 1):
        return nums[n - 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)

function missingElement(nums, k) {
  const n = nums.length;
  const missing = (i) => nums[i] - nums[0] - i;
  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 + hi) >> 1;
    if (missing(mid) < k) lo = mid + 1;
    else hi = mid;
  }
  return nums[lo - 1] + k - missing(lo - 1);
}

class Solution {
    public int missingElement(int[] nums, int k) {
        int n = nums.length;
        if (k > missing(nums, n - 1)) return nums[n - 1] + k - missing(nums, n - 1);
        int lo = 0, hi = n - 1;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (missing(nums, mid) < k) lo = mid + 1;
            else hi = mid;
        }
        return nums[lo - 1] + k - missing(nums, lo - 1);
    }
    private int missing(int[] nums, int i) {
        return nums[i] - nums[0] - i;
    }
}

int missingElement(vector<int>& nums, int k) {
    int n = nums.size();
    auto missing = [&](int i) { return nums[i] - nums[0] - i; };
    if (k > missing(n - 1)) return nums[n - 1] + k - missing(n - 1);
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (missing(mid) < k) lo = mid + 1;
        else hi = mid;
    }
    return nums[lo - 1] + k - missing(lo - 1);
}

Explanation

We want the k-th number that is missing from a sorted, distinct array, counting from nums[0]. The clever part is a formula that tells us, at any index i, how many numbers are missing before it.

That formula is missing(i) = nums[i] - nums[0] - i. In a perfect run with no gaps, nums[i] would equal nums[0] + i; the actual difference is exactly how many values got skipped up to index i. This count increases as i grows, so it is sorted and we can binary-search it.

First handle the easy case: if k exceeds missing(n-1), the answer is past the last element, so we just add the leftover to nums[n-1]. Otherwise we binary-search for the first index where missing(i) >= k. The k-th missing number then lies in the gap right after nums[lo-1], computed as nums[lo-1] + k - missing(lo-1).

Example: nums = [4,7,9,10], k = 3. The missing numbers are 5, 6, 8, 11, ... The search lands so that the gap after 7 holds the 3rd missing value, giving 7 + (3 - 2) = 8.

Because the missing-count is monotone, binary search finds the right gap in O(log n) instead of scanning every value.

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