3275. K-th Nearest Obstacle Queries LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3275. K-th Nearest Obstacle Queries LeetCode Solution with the best time and space complexity. The solution to K-th Nearest Obstacle Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
K-th Nearest Obstacle Queries solution in C++
K-th Nearest Obstacle Queries solution in Java
K-th Nearest Obstacle Queries solution in Python
Additional Resources

3275. K-th Nearest Obstacle Queries LeetCode Solution image

Problem Statement of K-th Nearest Obstacle Queries

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|.

Example 1:

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:

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 * 105
All queries[i] are unique.
-109 <= queries[i][0], queries[i][1] <= 109
1 <= k <= 105

Complexity Analysis

Time Complexity: O(q\log k)
Space Complexity: O(q)

3275. K-th Nearest Obstacle Queries LeetCode Solution in C++

class Solution {
 public:
  vector<int> resultsArray(vector<vector<int>>& queries, int k) {
    vector<int> ans;
    priority_queue<int> maxHeap;

    for (const vector<int>& query : queries) {
      const int x = query[0];
      const int y = query[1];
      maxHeap.push(abs(x) + abs(y));
      if (maxHeap.size() > k)
        maxHeap.pop();
      ans.push_back(maxHeap.size() == k ? maxHeap.top() : -1);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3275. K-th Nearest Obstacle Queries LeetCode Solution in Java

class Solution {
  public int[] resultsArray(int[][] queries, int k) {
    int[] ans = new int[queries.length];
    Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

    for (int i = 0; i < queries.length; ++i) {
      final int x = queries[i][0];
      final int y = queries[i][1];
      maxHeap.offer(Math.abs(x) + Math.abs(y));
      if (maxHeap.size() > k)
        maxHeap.poll();
      ans[i] = maxHeap.size() == k ? maxHeap.peek() : -1;
    }

    return ans;
  }
}
// code provided by PROGIEZ

3275. K-th Nearest Obstacle Queries LeetCode Solution in Python

class Solution:
  def resultsArray(self, queries: list[list[int]], k: int) -> list[int]:
    ans = []
    maxHeap = []

    for x, y in queries:
      heapq.heappush(maxHeap, -(abs(x) + abs(y)))
      if len(maxHeap) > k:
        heapq.heappop(maxHeap)
      ans.append(-maxHeap[0] if len(maxHeap) == k else -1)

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents