K-th Nearest Obstacle Queries - Video Solutions
K-th Nearest Obstacle Queries || LeetCode Weekly Contest 413 || Leetcode Solution
K-th Nearest Obstacle Queries - Video Solution
Watch 10 video solutions for K-th Nearest Obstacle Queries, a medium level problem involving Array, Heap (Priority Queue). This walkthrough by codi has 938 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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] <= 1091 <= k <= 105
Approach Overview
Problem 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.
Complexity Analysis
| 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 |