K th smallest remaining even integer in subarray queries

28.4% acceptance

May 13, 2026

You are given an integer array nums where nums is strictly increasing. You are also given a 2D integer array queries, where queries[i] = [li, ri, ki]. For each query [li, ri, ki]: Consider the subarray nums[li..ri] From the infinite sequence of all positive even integers: 2, 4, 6, 8, 10, 12, 14, ... Remove all elements that appear in the subarray nums[li..ri]. Find the kith smallest integer remaining in the sequence after the removals. Return an integer array ans, where ans[i] is the result for the ith query.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn kth_remaining_integer(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = nums.len();
    let mut even_prefix = vec![0i32; n + 1];
    for i in 0..n {
      even_prefix[i + 1] = even_prefix[i] + (if nums[i] % 2 == 0 { 1 } else { 0 });
    }
    let count_evens_in_range = |l: usize, r: usize| -> i64 {
      (even_prefix[r + 1] - even_prefix[l]) as i64
    };
    let count_evens_le_val = |l: usize, r: usize, v: i64| -> i64 {
      if (nums[l] as i64) > v { return 0; }
      let mut lo = l;
      let mut hi = r;
      while lo < hi {
        let mid = (lo + hi + 1) / 2;
        if (nums[mid] as i64) <= v { lo = mid; }
        else { hi = mid - 1; }
      }
      count_evens_in_range(l, lo)
    };
    let mut ans = Vec::with_capacity(queries.len());
    for q in queries {
      let l = q[0] as usize;
      let r = q[1] as usize;
      let k = q[2] as i64;
      let total_evens = count_evens_in_range(l, r);
      let mut lo = 1i64;
      let mut hi = k + total_evens;
      while lo < hi {
        let mid = (lo + hi) / 2;
        let v = 2 * mid;
        let c = count_evens_le_val(l, r, v);
        if mid - c >= k { hi = mid; }
        else { lo = mid + 1; }
      }
      ans.push((2 * lo) as i32);
    }
    ans
  }
}