K-th Nearest Obstacle Queries

Med

#2907Time: 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.

Data structures

Array Heap (Priority Queue)

Prompt

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 k^th nearest obstacle from the origin.

Return an integer array results where results[i] denotes the k^th 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 * 10⁵
All queries[i] are unique.
-10⁹ <= queries[i][0], queries[i][1] <= 10⁹
1 <= k <= 10⁵

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int[] kNearestObstacles(int[][] queries, int k) {7        int n = queries.length;8        int[] results = new int[n];9        List<Long> distances = new ArrayList<>();10 11        for (int i = 0; i < n; i++) {12            long x = queries[i][0];13            long y = queries[i][1];14            long dist = Math.abs(x) + Math.abs(y);15            distances.add(dist);16 17            if (distances.size() < k) {18                results[i] = -1;19            } else {20                List<Long> sortedDistances = new ArrayList<>(distances);21                Collections.sort(sortedDistances);22                results[i] = sortedDistances.get(k - 1).intValue();23            }24        }25        return results;26    }27}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1// This implementation uses a sorted list to simulate an Order Statistic Tree.2// The performance is O(N^2) due to list insertion, not the O(N log N) of a true OST.3import java.util.ArrayList;4import java.util.Collections;5import java.util.List;6 7class Solution {8    public int[] kNearestObstacles(int[][] queries, int k) {9        int n = queries.length;10        int[] results = new int[n];11        List<Long> sortedDistances = new ArrayList<>();12 13        for (int i = 0; i < n; i++) {14            long x = queries[i][0];15            long y = queries[i][1];16            long dist = Math.abs(x) + Math.abs(y);17 18            // Insert into sorted list to maintain order19            int insertionPoint = Collections.binarySearch(sortedDistances, dist);20            if (insertionPoint < 0) {21                insertionPoint = -(insertionPoint + 1);22            }23            sortedDistances.add(insertionPoint, dist);24 25            if (sortedDistances.size() < k) {26                results[i] = -1;27            } else {28                results[i] = sortedDistances.get(k - 1).intValue();29            }30        }31        return results;32    }33}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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().

1import java.util.PriorityQueue;2import java.util.Collections;3 4class Solution {5    public int[] kNearestObstacles(int[][] queries, int k) {6        int n = queries.length;7        int[] results = new int[n];8        // Max-heap to store the k smallest distances9        PriorityQueue<Long> maxHeap = new PriorityQueue<>(Collections.reverseOrder());10 11        for (int i = 0; i < n; i++) {12            long x = queries[i][0];13            long y = queries[i][1];14            long dist = Math.abs(x) + Math.abs(y);15 16            if (maxHeap.size() < k) {17                maxHeap.add(dist);18            } else if (dist < maxHeap.peek()) {19                maxHeap.poll();20                maxHeap.add(dist);21            }22 23            if (maxHeap.size() < k) {24                results[i] = -1;25            } else {26                results[i] = maxHeap.peek().intValue();27            }28        }29        return results;30    }31}

Complexity

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

Trade-offs

Pros

Highly efficient in both time and space.
Uses standard library data structures, making it easy to implement.
Optimal space complexity.

Cons

Solutions

Solution

1class Solution {2public3  int[] resultsArray(int[][] queries, int k) {4    int n = queries.length;5    int[] ans = new int[n];6    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());7    for (int i = 0; i < n; ++i) {8      int x = Math.abs(queries[i][0]) + Math.abs(queries[i][1]);9      pq.offer(x);10      if (i >= k) {11        pq.poll();12      }13      ans[i] = i >= k - 1 ? pq.peek() : -1;14    }15    return ans;16  }17}

1class Solution {2public:3  vector<int> resultsArray(vector<vector<int>> &queries, int k) {4    vector<int> ans;5    priority_queue<int> pq;6    for (const auto &q : queries) {7      int x = abs(q[0]) + abs(q[1]);8      pq.push(x);9      if (pq.size() > k) {10        pq.pop();11      }12      ans.push_back(pq.size() == k ? pq.top() : -1);13    }14    return ans;15  }16};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int[] resultsArray(int[][] queries, int k) {4    int n = queries.length;5    int[] ans = new int[n];6    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());7    for (int i = 0; i < n; ++i) {8      int x = Math.abs(queries[i][0]) + Math.abs(queries[i][1]);9      pq.offer(x);10      if (i >= k) {11        pq.poll();12      }13      ans[i] = i >= k - 1 ? pq.peek() : -1;14    }15    return ans;16  }17}

1class Solution {2public:3  vector<int> resultsArray(vector<vector<int>> &queries, int k) {4    vector<int> ans;5    priority_queue<int> pq;6    for (const auto &q : queries) {7      int x = abs(q[0]) + abs(q[1]);8      pq.push(x);9      if (pq.size() > k) {10        pq.pop();11      }12      ans.push_back(pq.size() == k ? pq.top() : -1);13    }14    return ans;15  }16};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.