What is the K-th Nearest Obstacle Queries problem?

The K-th Nearest Obstacle Queries problem involves finding the distance of the k-th nearest obstacle from the origin in an infinite 2D plane, given multiple queries.

How does a heap help with the K-th Nearest Obstacle Queries?

A heap (priority queue) helps efficiently track the k-th nearest distance by storing the smallest k distances and quickly updating them as new queries arrive.

What is the time complexity of solving this problem?

The time complexity is O(n log k), where n is the number of queries, and k is the number of closest obstacles to track.

Why not use sorting for K-th Nearest Obstacle Queries?

Sorting all distances after each query is less efficient than using a heap because it has a time complexity of O(n log n), whereas heap operations can be performed in O(log k) time.

Can GhostInterview help optimize solutions for this problem?

Yes, GhostInterview provides guidance on selecting the optimal data structure and method, focusing on performance improvements through heap-based solutions for the K-th Nearest Obstacle Queries.

#3275

Medium

auto_awesome堆

LeetCode 题解工作台

第 K 近障碍物查询

有一个无限大的二维平面。给你一个正整数 k ，同时给你一个二维数组 queries ，包含一系列查询： queries[i] = [x, y] ：在平面上坐标 (x, y) 处建一个障碍物，数据保证之前的查询不会在这个坐标处建立任何障碍物。每次查询后，你需要找到离原点第 k 近障碍物到原点…

数组堆（优先队列）

题目描述

有一个无限大的二维平面。

给你一个正整数 k ，同时给你一个二维数组 queries ，包含一系列查询：

queries[i] = [x, y] ：在平面上坐标 (x, y) 处建一个障碍物，数据保证之前的查询不会在这个坐标处建立任何障碍物。

每次查询后，你需要找到离原点第 k 近障碍物到原点的距离。

请你返回一个整数数组 results ，其中 results[i] 表示建立第 i 个障碍物以后，离原地第 k 近障碍物距离原点的距离。如果少于 k 个障碍物，results[i] == -1 。

注意，一开始没有任何障碍物。

坐标在 (x, y) 处的点距离原点的距离定义为 |x| + |y| 。

示例 1：

输入：queries = [[1,2],[3,4],[2,3],[-3,0]], k = 2

输出：[-1,7,5,3]

解释：

最初，不存在障碍物。

queries[0] 之后，少于 2 个障碍物。
queries[1] 之后，两个障碍物距离原点的距离分别为 3 和 7 。
queries[2] 之后，障碍物距离原点的距离分别为 3 ，5 和 7 。
queries[3] 之后，障碍物距离原点的距离分别为 3，3，5 和 7 。

示例 2：

输入：queries = [[5,5],[4,4],[3,3]], k = 1

输出：[10,8,6]

解释：

queries[0] 之后，只有一个障碍物，距离原点距离为 10 。
queries[1] 之后，障碍物距离原点距离分别为 8 和 10 。
queries[2] 之后，障碍物距离原点的距离分别为 6， 8 和10 。

提示：

1 <= queries.length <= 2 * 10⁵
所有 queries[i] 互不相同。
-10⁹ <= queries[i][0], queries[i][1] <= 10⁹
1 <= k <= 10⁵

lightbulb

解题思路

方法一：优先队列（大根堆）

我们可以使用一个优先队列（大根堆）来维护离原点最近的 $k$ 个障碍物。

遍历 $\textit{queries}$ ，每次计算 $x$ 和 $y$ 的绝对值之和，然后将其加入优先队列。如果优先队列的大小超过 $k$ ，则弹出堆顶元素。如果当前优先队列的大小等于 $k$ ，则将堆顶元素加入答案数组，否则将 $-1$ 加入答案数组。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n \times \log k)$ ，空间复杂度 $O(k)$ 。其中 $n$ 为数组 $\textit{queries}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def resultsArray(self, queries: List[List[int]], k: int) -> List[int]:
        ans = []
        pq = []
        for i, (x, y) in enumerate(queries):
            heappush(pq, -(abs(x) + abs(y)))
            if i >= k:
                heappop(pq)
            ans.append(-pq[0] if i >= k - 1 else -1)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate consider heap-based solutions to optimize the k-th nearest distance?
question_mark
Does the candidate evaluate the trade-offs between heap and sorting approaches?
question_mark
How efficiently does the candidate handle multiple queries with large inputs?

warning

常见陷阱

外企场景

error
Not using the heap efficiently, leading to suboptimal performance for large inputs.
error
Incorrectly assuming that sorting all obstacles will be faster than using a heap for k-th nearest calculations.
error
Overcomplicating the solution by not considering that only the k closest obstacles matter for each query.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the value of k is very large? Can the approach handle it efficiently?
arrow_right_alt
How would the solution change if obstacles were added dynamically after each query?
arrow_right_alt
What if the query coordinates themselves were to change during the problem?

help

常见问题

外企场景

继续练习

#3266 K 次乘运算后的最终数组 II #3264 K 次乘运算后的最终数组 I #3286 穿越网格图的安全路径