Problem

There is an infinite 2D plane.

You are given a positive integer k. You are also given a 2D array queries, which contains the following queries:

  • queries[i] = [x, y]: Build an obstacle at coordinate (x, y) in the plane. It is guaranteed that there is no obstacle at this coordinate when this query is made.

After each query, you need to find the distance of the kth nearest obstacle from the origin.

Return an integer array results where results[i] denotes the kth nearest obstacle after query i, or results[i] == -1 if there are less than k obstacles.

Note that initially there are no obstacles anywhere.

The distance of an obstacle at coordinate (x, y) from the origin is given by |x| + |y|.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: queries = [[1,2],[3,4],[2,3],[-3,0]], k = 2

Output: [-1,7,5,3]

Explanation:

  * Initially, there are 0 obstacles.
  * After `queries[0]`, there are less than 2 obstacles.
  * After `queries[1]`, there are obstacles at distances 3 and 7.
  * After `queries[2]`, there are obstacles at distances 3, 5, and 7.
  * After `queries[3]`, there are obstacles at distances 3, 3, 5, and 7.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: queries = [[5,5],[4,4],[3,3]], k = 1

Output: [10,8,6]

Explanation:

  * After `queries[0]`, there is an obstacle at distance 10.
  * After `queries[1]`, there are obstacles at distances 8 and 10.
  * After `queries[2]`, there are obstacles at distances 6, 8, and 10.

Constraints

  • 1 <= queries.length <= 2 * 10^5
  • All queries[i] are unique.
  • -109 <= queries[i][0], queries[i][1] <= 10^9
  • 1 <= k <= 10^5

Solution

Method 1 – Max-Heap for K-th Nearest Tracking

Intuition

To efficiently track the k-th nearest obstacle after each query, use a max-heap (priority queue) of size at most k. The heap always contains the k smallest distances seen so far, so the top is the k-th nearest. If fewer than k obstacles, return -1.

Approach

  1. Initialize an empty max-heap (priority queue) for distances.
  2. For each query, compute the Manhattan distance from the origin.
  3. Add the distance to the heap. If the heap size exceeds k, remove the largest (top) element.
  4. After each query, if the heap has at least k elements, the k-th nearest is the top; otherwise, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    vector<int> kthNearestObstacle(vector<vector<int>>& queries, int k) {
        priority_queue<int> pq;
        vector<int> ans;
        for (auto& q : queries) {
            int d = abs(q[0]) + abs(q[1]);
            pq.push(d);
            if (pq.size() > k) pq.pop();
            ans.push_back(pq.size() == k ? pq.top() : -1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import "container/heap"
type MaxHeap []int
func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any          { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
func kthNearestObstacle(queries [][]int, k int) []int {
    h := &MaxHeap{}
    heap.Init(h)
    ans := make([]int, 0, len(queries))
    for _, q := range queries {
        d := abs(q[0]) + abs(q[1])
        heap.Push(h, d)
        if h.Len() > k { heap.Pop(h) }
        if h.Len() == k {
            ans = append(ans, (*h)[0])
        } else {
            ans = append(ans, -1)
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public List<Integer> kthNearestObstacle(int[][] queries, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        List<Integer> ans = new ArrayList<>();
        for (int[] q : queries) {
            int d = Math.abs(q[0]) + Math.abs(q[1]);
            pq.offer(d);
            if (pq.size() > k) pq.poll();
            ans.add(pq.size() == k ? pq.peek() : -1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun kthNearestObstacle(queries: Array<IntArray>, k: Int): List<Int> {
        val pq = java.util.PriorityQueue<Int>(compareByDescending { it })
        val ans = mutableListOf<Int>()
        for (q in queries) {
            val d = kotlin.math.abs(q[0]) + kotlin.math.abs(q[1])
            pq.add(d)
            if (pq.size > k) pq.poll()
            ans.add(if (pq.size == k) pq.peek() else -1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import heapq
class Solution:
    def kthNearestObstacle(self, queries: list[list[int]], k: int) -> list[int]:
        pq: list[int] = []
        ans: list[int] = []
        for x, y in queries:
            d = abs(x) + abs(y)
            heapq.heappush(pq, -d)
            if len(pq) > k:
                heapq.heappop(pq)
            ans.append(-pq[0] if len(pq) == k else -1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

use std::collections::BinaryHeap;
impl Solution {
    pub fn kth_nearest_obstacle(queries: Vec<Vec<i32>>, k: i32) -> Vec<i32> {
        let mut pq = BinaryHeap::new();
        let mut ans = vec![];
        for q in queries {
            let d = q[0].abs() + q[1].abs();
            pq.push(d);
            if pq.len() > k as usize { pq.pop(); }
            ans.push(if pq.len() == k as usize { *pq.peek().unwrap() } else { -1 });
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    kthNearestObstacle(queries: number[][], k: number): number[] {
        const pq: number[] = [];
        const ans: number[] = [];
        for (const [x, y] of queries) {
            const d = Math.abs(x) + Math.abs(y);
            pq.push(d);
            pq.sort((a, b) => b - a);
            if (pq.length > k) pq.shift();
            ans.push(pq.length === k ? pq[0] : -1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log k), where n is the number of queries. Each heap operation is O(log k).
  • 🧺 Space complexity: O(k), for the heap storing up to k distances.