K-th Nearest Obstacle Queries

K-th Nearest Obstacle Queries

1. What is this problem about?

The K-th Nearest Obstacle Queries interview question is a dynamic distance-tracking task. You are at the origin $(0, 0)$ and a stream of obstacles is added one by one at various coordinates. For each new obstacle, you need to find the $k^{th}$ smallest Manhattan distance among all obstacles seen so far. If fewer than $k$ obstacles exist, return -1.

2. Why is this asked in interviews?

Google ask this Obstacle Queries coding problem to evaluate your ability to maintain a sorted subset of a data stream. It tests your knowledge of Heaps (Priority Queues). The goal is to efficiently find the $k^{th}$ smallest value without sorting the entire history of obstacles ($O(N \log N)$ per query).

3. Algorithmic pattern used

This problem follows the Max-Heap for Top-K Smallest pattern.

1. Initialize: Maintain a Max-Heap of size $k$.
2. Process: For each new obstacle at $(x, y)$:
   • Calculate Manhattan distance: $|x| + |y|$.
   • Push the distance into the Max-Heap.
   • If the heap size exceeds $k$, pop the largest element.
3. Query: If the heap size is exactly $k$, the top of the Max-Heap is the $k^{th}$ smallest distance. If not, return -1.

4. Example explanation

$k = 2$, Obstacles at: [1, 2], [3, 4], [0, 1]

1. Obstacle [1, 2]: dist 3. Heap: [3]. Return -1 (size < 2).
2. Obstacle [3, 4]: dist 7. Heap: [7, 3]. Top is 7. Return 7.
3. Obstacle [0, 1]: dist 1. Heap: [7, 3, 1]. Pop 7. Heap: [3, 1]. Top is 3. Return 3. Result: [-1, 7, 3].

5. Common mistakes candidates make

• Using a Min-Heap: A Min-Heap gives you the smallest element, but to keep the $k$ smallest elements and find the largest among them (the $k^{th}$ smallest), you need a Max-Heap.
• Sorting every time: Re-sorting the whole list of distances for each query ($O(N^2 \log N)$ total), which is too slow.
• Incorrect Distance: Using Euclidean distance when the problem specifies Manhattan.

6. Interview preparation tip

Master the "Top-K" pattern. To find the $k$ smallest things, use a Max-Heap. To find the $k$ largest things, use a Min-Heap. This is a foundational Heap interview pattern for data stream processing.