# K-th Nearest Obstacle Queries
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/k-th-nearest-obstacle-queries)
Canonical: https://scaleengineer.com/dsa/problems/k-th-nearest-obstacle-queries
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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] <= 109`
* `1 <= k <= 105`

# Approaches
## Brute Force by Sorting After Each Query
A straightforward approach is to maintain a list of all obstacle distances encountered so far. After each query, a new obstacle is added, its distance from the origin is calculated and appended to the list. If the number of obstacles is at least `k`, the entire list of distances is sorted, and the k-th element (at index `k-1`) is selected as the answer for the current query.
**Time:** O(N^2 log N), where N is the number of queries. For each query `i` (from 0 to N-1), we add a distance and then sort a list of size `i+1`. Sorting takes `O(i log i)`. The total time is the sum `Σ O(i log i)` for `i` from 1 to N, which is approximately `O(N^2 log N)`. · **Space:** O(N), where N is the number of queries. We need to store all the distances calculated so far.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient due to repeated sorting of a growing list.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
This method simulates the process directly. We use a dynamic array (like `ArrayList` in Java) to keep track of the distances of all obstacles placed so far. For each of the `N` queries, we compute the new obstacle's Manhattan distance and add it to our list. Then, if we have at least `k` obstacles, we sort the list to find the k-th smallest distance. While simple, the cost of sorting grows with each query, leading to poor overall performance.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] kNearestObstacles(int[][] queries, int k) {
        int n = queries.length;
        int[] results = new int[n];
        List<Long> distances = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            long x = queries[i][0];
            long y = queries[i][1];
            long dist = Math.abs(x) + Math.abs(y);
            distances.add(dist);

            if (distances.size() < k) {
                results[i] = -1;
            } else {
                List<Long> sortedDistances = new ArrayList<>(distances);
                Collections.sort(sortedDistances);
                results[i] = sortedDistances.get(k - 1).intValue();
            }
        }
        return results;
    }
}
```
### Algorithm
*   Initialize an empty list `distances` to store the Manhattan distances of all obstacles.
*   Initialize an empty array `results` to store the answer for each query.
*   For each `query = [x, y]` in `queries`:
    *   Calculate the distance `d = |x| + |y|`.
    *   Add `d` to the `distances` list.
    *   If the number of elements in `distances` is less than `k`, add `-1` to `results`.
    *   Otherwise, create a copy of `distances`, sort it in non-decreasing order, and find the element at index `k-1`. Add this element to `results`.
*   Return `results`.

## Using an Order Statistic Tree
This approach improves upon the brute-force method by using a more suitable data structure. Instead of sorting the entire list of distances at each step, we can maintain them in a data structure that allows for efficient insertions and retrieval of the k-th smallest element. An Order Statistic Tree, which is a balanced binary search tree augmented to support finding the element of a specific rank, is well-suited for this.
**Time:** O(N log N). With a proper Order Statistic Tree, each insertion and rank query takes `O(log i)` time, where `i` is the current number of elements. Summing over `N` queries gives a total time complexity of `Σ O(log i) = O(log(N!)) = O(N log N)`. · **Space:** O(N), as the tree needs to store all N distances.
**Pros:** Significantly faster than the brute-force approach.; Logarithmic time complexity per query with a proper implementation.
**Cons:** Requires a specialized data structure (Order Statistic Tree) which is not available in Java's standard library.; The space complexity of O(N) is not optimal.
### Explanation
An Order Statistic Tree can perform insertions and find the k-th smallest element (a rank query) in logarithmic time relative to the number of elements in the tree. For each query, we calculate the new distance and insert it into the tree. Then, we query the tree for the element at rank `k-1`.

Since Java's standard library lacks a native Order Statistic Tree, one would need to implement it or use a third-party library. The code below simulates the behavior using a sorted `ArrayList` for demonstration, but note that this simulation has `O(i)` insertion time, leading to an overall `O(N^2)` complexity, not the `O(N log N)` of a true Order Statistic Tree.

```java
// This implementation uses a sorted list to simulate an Order Statistic Tree.
// The performance is O(N^2) due to list insertion, not the O(N log N) of a true OST.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] kNearestObstacles(int[][] queries, int k) {
        int n = queries.length;
        int[] results = new int[n];
        List<Long> sortedDistances = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            long x = queries[i][0];
            long y = queries[i][1];
            long dist = Math.abs(x) + Math.abs(y);

            // Insert into sorted list to maintain order
            int insertionPoint = Collections.binarySearch(sortedDistances, dist);
            if (insertionPoint < 0) {
                insertionPoint = -(insertionPoint + 1);
            }
            sortedDistances.add(insertionPoint, dist);

            if (sortedDistances.size() < k) {
                results[i] = -1;
            } else {
                results[i] = sortedDistances.get(k - 1).intValue();
            }
        }
        return results;
    }
}
```
### Algorithm
*   Initialize an empty Order Statistic Tree `ost`.
*   Initialize an empty array `results`.
*   For each `query = [x, y]` in `queries`:
    *   Calculate the distance `d = |x| + |y|`.
    *   Insert `d` into the `ost`.
    *   If the size of `ost` is less than `k`, add `-1` to `results`.
    *   Otherwise, find the element at the `(k-1)`-th rank in the `ost` and add it to `results`.
*   Return `results`.

## Optimal Approach using a Max-Heap
The most efficient approach for this problem uses a max-heap (a `PriorityQueue` in Java configured as a max-heap). This problem is a classic example of finding the 'k-th smallest element in a stream'. A max-heap is perfect for maintaining the `k` smallest elements seen so far.
**Time:** O(N log k). For each of the `N` queries, we perform at most one `add` and one `poll` operation on the heap. Since the heap's size is capped at `k`, these operations take `O(log k)` time. · **Space:** O(k). The max-heap stores at most `k` distances. This is optimal in terms of space, especially when `k` is much smaller than `N`.
**Pros:** Highly efficient in both time and space.; Uses standard library data structures, making it easy to implement.; Optimal space complexity.
### Explanation
We maintain a max-heap of size at most `k`. The top of the max-heap will always be the largest among the `k` smallest elements found so far. For each new obstacle's distance, we compare it with the top of the heap.

*   If the heap has fewer than `k` elements, we simply add the new distance.
*   If the heap is full (size `k`) and the new distance is smaller than the heap's maximum, we know the new distance belongs in our set of `k` smallest. We remove the maximum element and insert the new, smaller distance. This keeps the heap's invariant.
*   If the new distance is larger than or equal to the heap's maximum, we discard it, as it cannot be one of the `k` smallest.

After processing each query, if the heap size is `k`, the k-th smallest distance is precisely the maximum element in the heap, which can be retrieved in `O(1)` time using `peek()`.

```java
import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int[] kNearestObstacles(int[][] queries, int k) {
        int n = queries.length;
        int[] results = new int[n];
        // Max-heap to store the k smallest distances
        PriorityQueue<Long> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < n; i++) {
            long x = queries[i][0];
            long y = queries[i][1];
            long dist = Math.abs(x) + Math.abs(y);

            if (maxHeap.size() < k) {
                maxHeap.add(dist);
            } else if (dist < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.add(dist);
            }

            if (maxHeap.size() < k) {
                results[i] = -1;
            } else {
                results[i] = maxHeap.peek().intValue();
            }
        }
        return results;
    }
}
```
### Algorithm
*   Initialize a max-heap `maxHeap`. In Java, this is a `PriorityQueue` with a reverse order comparator.
*   Initialize an empty array `results`.
*   For each `query = [x, y]` in `queries`:
    *   Calculate the distance `d = |x| + |y|`.
    *   If `maxHeap.size() < k`, add `d` to the heap.
    *   Else if `d < maxHeap.peek()`, it means `d` is one of the `k` smallest distances, so remove the current largest (`maxHeap.poll()`) and add `d`.
    *   After updating the heap, check its size. If `maxHeap.size() < k`, the result for this query is `-1`.
    *   Otherwise, the result is the largest element in the heap (`maxHeap.peek()`), which is the k-th smallest distance overall.
*   Store the result and continue to the next query.
*   Return the `results` array.

# Solutions
### Java

```java
class Solution {
public
  int[] resultsArray(int[][] queries, int k) {
    int n = queries.length;
    int[] ans = new int[n];
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    for (int i = 0; i < n; ++i) {
      int x = Math.abs(queries[i][0]) + Math.abs(queries[i][1]);
      pq.offer(x);
      if (i >= k) {
        pq.poll();
      }
      ans[i] = i >= k - 1 ? pq.peek() : -1;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> resultsArray(vector<vector<int>> &queries, int k) {
    vector<int> ans;
    priority_queue<int> pq;
    for (const auto &q : queries) {
      int x = abs(q[0]) + abs(q[1]);
      pq.push(x);
      if (pq.size() > k) {
        pq.pop();
      }
      ans.push_back(pq.size() == k ? pq.top() : -1);
    }
    return ans;
  }
};

```

### Python

```python
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

```