K-th Nearest Obstacle Queries
There is an infinite 2D plane.
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|.
Example 1
Input: queries = [[1,2],[3,4],[2,3],[-3,0]], k = 2
Output: [-1,7,5,3]
Example 2
Input: queries = [[5,5],[4,4],[3,3]], k = 1
Output: [10,8,6]
Constraints
- 1 <= queries.length <= 2 * 10^5
- All queries[i] are unique.
- -10^9 <= queries[i][0], queries[i][1] <= 10^9
- 1 <= k <= 10^5
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.