Scale Engineer

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
ArrayHeap (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 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

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.

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;    }}

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.

Solutions

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;  }}

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 →

Next problem