K-th Nearest Obstacle Queries - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3275. K-th Nearest Obstacle Queries
Medium
30 Points
Array
Heap (Priority Queue)
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:
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|.
Examples
Example 1
Input: queries = [[1,2],[3,4],[2,3],[-3,0]], k = 2
Output: [-1,7,5,3]
Explanation:
Example 2
Input: queries = [[5,5],[4,4],[3,3]], k = 1
Output: [10,8,6]
Explanation:
Constraints
1 <= queries.length <= 2 * 105
All queries[i] are unique.
-109 <= queries[i][0], queries[i][1] <= 109
1 <= k <= 105
3275. K-th Nearest Obstacle Queries
Medium
30 Points
Array
Heap (Priority Queue)
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:
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|.
Examples
Example 1
Input: queries = [[1,2],[3,4],[2,3],[-3,0]], k = 2
Output: [-1,7,5,3]
Explanation:
Example 2
Input: queries = [[5,5],[4,4],[3,3]], k = 1
Output: [10,8,6]
Explanation: