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:
queries[0], there are less than 2 obstacles.queries[1], there are obstacles at distances 3 and 7.queries[2], there are obstacles at distances 3, 5, and 7.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:
queries[0], there is an obstacle at distance 10.queries[1], there are obstacles at distances 8 and 10.queries[2], there are obstacles at distances 6, 8, and 10.
Constraints:
1 <= queries.length <= 2 * 105queries[i] are unique.-109 <= queries[i][0], queries[i][1] <= 1091 <= k <= 105Problem Overview: Each query adds an obstacle at coordinate (x, y). After every insertion, you must report the distance of the k-th nearest obstacle from the origin. If fewer than k obstacles exist, return -1. The challenge is maintaining the k-th closest distance efficiently as new points arrive.
Approach 1: Min-Heap of All Distances (O(n log n) time, O(n) space)
Compute the distance of every obstacle from the origin using |x| + |y|. Push each distance into a min-heap. To determine the k-th nearest obstacle, temporarily remove the smallest element k times from the heap; the last popped value is the answer. This approach directly uses a heap (priority queue) to maintain sorted order of distances.
The drawback is repeated heap operations. For every query you may perform up to k extra pops, which increases the runtime significantly when the number of obstacles grows. The heap also stores all distances, so memory grows linearly with the number of queries.
Approach 2: Max-Heap of Size k (O(n log k) time, O(k) space)
Track only the k closest obstacles using a max-heap. For each query, compute the distance and push it into the heap. If the heap size exceeds k, remove the largest element. This ensures the heap always stores the k smallest distances seen so far.
The top of the max-heap represents the current k-th nearest obstacle. If the heap size is less than k, return -1. Otherwise return the heap's maximum value. This technique avoids storing unnecessary distances and limits heap operations to log k. It works well for streaming queries where new elements continuously arrive.
The approach combines efficient heap maintenance with incremental updates to the answer. You process each query once, perform at most one insertion and one removal, and read the result from the heap top.
Problems like this appear frequently in interview settings where you must maintain a dynamic k-th statistic. The same pattern appears in tasks involving arrays with online updates and top-k tracking using priority queues.
Recommended for interviews: The max-heap of size k is the expected solution. It demonstrates understanding of streaming data structures and k-th element maintenance. Explaining the full min-heap approach first shows baseline reasoning, but the bounded max-heap shows optimization and practical heap usage.
A min-heap or priority queue can efficiently manage the smallest elements in a dynamic list. With each query, we calculate the distance of new obstacles and use a min-heap to store them. By maintaining a heap of size not exceeding k, we can determine the k-th closest distance efficiently. If the heap size is less than k, return -1, else return the root of the heap.
The Python implementation uses the heapq module, which supports min-heap operations. We push distances to the heap and maintain a check on its size. If the size reaches k, the root of the heap (the smallest element) would be the k-th nearest distance. If the size is less, we return -1.
Time Complexity: O(n log k), where n is the number of queries. Each insertion into the heap takes log k time.
Space Complexity: O(k), to store the heap of k elements.
Another approach is to use a max-heap to store the smallest k distances. This way, the root of the heap represents the k-th closest obstacle. If a new distance is smaller than the root of the heap, it replaces the root, keeping only the smallest k distances in the heap.
The C++ solution uses a max-heap to manage the smallest k elements efficiently. When the heap's size exceeds k, we pop the largest element. The root element then represents the k-th nearest after any query.
C++
JavaScript
Time Complexity: O(n log k), for managing k elements per query.
Space Complexity: O(k), maintaining the heap of k elements.
We can use a priority queue (max-heap) to maintain the k obstacles closest to the origin.
Traverse queries, and for each query, calculate the sum of the absolute values of x and y, then add it to the priority queue. If the size of the priority queue exceeds k, pop the top element. If the current size of the priority queue is equal to k, add the top element to the answer array; otherwise, add -1 to the answer array.
After the traversal, return the answer array.
The time complexity is O(n times log k), and the space complexity is O(k). Here, n is the length of the array queries.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using a Min-Heap (Priority Queue) | Time Complexity: O(n log k), where n is the number of queries. Each insertion into the heap takes log k time. |
| Using a Max-Heap (Inverse Priority Queue) | Time Complexity: O(n log k), for managing k elements per query. |
| Priority Queue (Max-Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap storing all distances | O(n log n) | O(n) | Simple implementation when constraints are small and storing all distances is acceptable |
| Max-Heap of size k | O(n log k) | O(k) | Best for streaming queries and large inputs where only the k closest obstacles matter |
K-th Nearest Obstacle Queries || LeetCode Weekly Contest 413 || Leetcode Solution • codi • 937 views views
Watch 9 more video solutions →Practice K-th Nearest Obstacle Queries with our built-in code editor and test cases.
Practice on FleetCode