Missing element in sorted array

Array Binary Search

59.7% acceptance

Mar 31, 2026

1738

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

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn missing_element(nums: Vec<i32>, k: i32) -> i32 {
    // missing(i) = count of missing numbers between nums[0] and nums[i]
    //            = nums[i] - nums[0] - i
    let n = nums.len();
    let missing = |i: usize| nums[i] - nums[0] - i as i32;
    if missing(n - 1) < k {
      return nums[n - 1] + (k - missing(n - 1));
    }
    let mut lo = 0usize;
    let mut hi = n - 1;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if missing(mid) < k {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }
    // lo is the first index where missing(lo) >= k
    // answer is between nums[lo-1] and nums[lo]
    nums[lo - 1] + (k - missing(lo - 1))
  }
}