LeetCode 3275: K-th Nearest Obstacle Queries Solution

Master LeetCode problem 3275 (K-th Nearest Obstacle Queries), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3275. K-th Nearest Obstacle Queries

Medium

Array Heap (Priority Queue)

Problem Explanation

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:

Initialize a priority queue to store the distances of obstacles from the origin.
Iterate through each query.
For each query, calculate the distance of the new obstacle from the origin and add it to the priority queue.
If the size of the priority queue is greater than k, pop the top element to maintain only k elements in the queue.
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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3275 (K-th Nearest Obstacle Queries)?

This page provides optimized solutions for LeetCode problem 3275 (K-th Nearest Obstacle Queries) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3275 (K-th Nearest Obstacle Queries)?

The time complexity for LeetCode 3275 (K-th Nearest Obstacle Queries) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3275 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3275 in Java, C++, or Python.

Back to LeetCode Solutions