LeetCode 3275: K-th Nearest Obstacle Queries

Explanation

To solve this problem, we can maintain a priority queue (min heap) to keep track of the distances of obstacles from the origin. As we process each query to build an obstacle, we calculate the distance of the new obstacle from the origin and add it to the priority queue. We then pop the kth nearest obstacle from the priority queue to get the answer for that query.

Steps:

1. Initialize a priority queue to store the distances of obstacles from the origin.
2. Iterate through each query.
3. For each query, calculate the distance of the new obstacle from the origin and add it to the priority queue.
4. If the size of the priority queue is greater than k, pop the top element to maintain only k elements in the queue.
5. Store the kth nearest obstacle distance in the results array.

Time Complexity: O(n log k) where n is the number of queries and k is the value of k. Space Complexity: O(k) for the priority queue.

import java.util.*;

class Solution {
    public int[] kthNearestObstacleQueries(int[][] queries, int k) {
        PriorityQueue<Integer> distances = new PriorityQueue<>(k, Collections.reverseOrder());
        int[] results = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0];
            int y = queries[i][1];
            int distance = Math.abs(x) + Math.abs(y);
            distances.add(distance);

            if (distances.size() > k) {
                distances.poll();
            }

            results[i] = distances.size() < k ? -1 : distances.peek();
        }

        return results;
    }
}