Kth missing positive number

Array Binary Search

63.2% acceptance

Feb 25, 2026

7921

574

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k. Return the kth positive integer that is missing from this array.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_kth_positive(arr: Vec<i32>, k: i32) -> i32 {
    // missing_count(x) = x - number of arr elements <= x
    let missing = |x: i32| -> i32 {
      x - arr.partition_point(|&y| y <= x) as i32
    };
    let mut lo = 1i32;
    let mut hi = 2001i32;
    while lo < hi {
      let mid = (lo + hi) / 2;
      if missing(mid) >= k { hi = mid; } else { lo = mid + 1; }
    }
    lo
  }
}