K th nearest obstacle queries

Array Heap (Priority Queue)

48.9% acceptance

Feb 25, 2026

116

There is an infinite 2D plane. After each query [x,y], add obstacle at Manhattan distance |x|+|y|. Find the k-th nearest obstacle distance (or -1 if < k obstacles).

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn results_array(queries: Vec<Vec<i32>>, k: i32) -> Vec<i32> {
    let k = k as usize;
    // Use a max-heap of size k to track k smallest distances
    let mut heap: std::collections::BinaryHeap<i32> = std::collections::BinaryHeap::new();
    let mut result = Vec::with_capacity(queries.len());
    for q in &queries {
      let d = q[0].abs() + q[1].abs();
      if heap.len() < k {
        heap.push(d);
      } else if let Some(&top) = heap.peek() {
        if d < top {
          heap.pop();
          heap.push(d);
        }
      }
      if heap.len() < k {
        result.push(-1);
      } else {
        result.push(*heap.peek().unwrap());
      }
    }
    result
  }
}