Skip to main content
Talentd

K-th Nearest Obstacle Queries - Solution & Explanation

MediumArrayHeap (Priority Queue)12 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Each query adds an obstacle at coordinate (x, y). After every insertion, you must report the distance of the k-th nearest obstacle from the origin. If fewer than k obstacles exist, return -1. The challenge is maintaining the k-th closest distance efficiently as new points arrive.

Approach 1: Min-Heap of All Distances (O(n log n) time, O(n) space)

Compute the distance of every obstacle from the origin using |x| + |y|. Push each distance into a min-heap. To determine the k-th nearest obstacle, temporarily remove the smallest element k times from the heap; the last popped value is the answer. This approach directly uses a heap (priority queue) to maintain sorted order of distances.

The drawback is repeated heap operations. For every query you may perform up to k extra pops, which increases the runtime significantly when the number of obstacles grows. The heap also stores all distances, so memory grows linearly with the number of queries.

Approach 2: Max-Heap of Size k (O(n log k) time, O(k) space)

Track only the k closest obstacles using a max-heap. For each query, compute the distance and push it into the heap. If the heap size exceeds k, remove the largest element. This ensures the heap always stores the k smallest distances seen so far.

The top of the max-heap represents the current k-th nearest obstacle. If the heap size is less than k, return -1. Otherwise return the heap's maximum value. This technique avoids storing unnecessary distances and limits heap operations to log k. It works well for streaming queries where new elements continuously arrive.

The approach combines efficient heap maintenance with incremental updates to the answer. You process each query once, perform at most one insertion and one removal, and read the result from the heap top.

Problems like this appear frequently in interview settings where you must maintain a dynamic k-th statistic. The same pattern appears in tasks involving arrays with online updates and top-k tracking using priority queues.

Recommended for interviews: The max-heap of size k is the expected solution. It demonstrates understanding of streaming data structures and k-th element maintenance. Explaining the full min-heap approach first shows baseline reasoning, but the bounded max-heap shows optimization and practical heap usage.

Approach 1: Using a Min-Heap (Priority Queue)

A min-heap or priority queue can efficiently manage the smallest elements in a dynamic list. With each query, we calculate the distance of new obstacles and use a min-heap to store them. By maintaining a heap of size not exceeding k, we can determine the k-th closest distance efficiently. If the heap size is less than k, return -1, else return the root of the heap.

The Python implementation uses the heapq module, which supports min-heap operations. We push distances to the heap and maintain a check on its size. If the size reaches k, the root of the heap (the smallest element) would be the k-th nearest distance. If the size is less, we return -1.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log k), where n is the number of queries. Each insertion into the heap takes log k time.
Space Complexity: O(k), to store the heap of k elements.

Try this approach in the editor →

Approach 2: Using a Max-Heap (Inverse Priority Queue)

Another approach is to use a max-heap to store the smallest k distances. This way, the root of the heap represents the k-th closest obstacle. If a new distance is smaller than the root of the heap, it replaces the root, keeping only the smallest k distances in the heap.

The C++ solution uses a max-heap to manage the smallest k elements efficiently. When the heap's size exceeds k, we pop the largest element. The root element then represents the k-th nearest after any query.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n log k), for managing k elements per query.
Space Complexity: O(k), maintaining the heap of k elements.

Try this approach in the editor →

Approach 3: Priority Queue (Max-Heap)

We can use a priority queue (max-heap) to maintain the k obstacles closest to the origin.

Traverse queries, and for each query, calculate the sum of the absolute values of x and y, then add it to the priority queue. If the size of the priority queue exceeds k, pop the top element. If the current size of the priority queue is equal to k, add the top element to the answer array; otherwise, add -1 to the answer array.

After the traversal, return the answer array.

The time complexity is O(n times log k), and the space complexity is O(k). Here, n is the length of the array queries.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using a Min-Heap (Priority Queue)

Time Complexity: O(n log k), where n is the number of queries. Each insertion into the heap takes log k time.
Space Complexity: O(k), to store the heap of k elements.

Using a Max-Heap (Inverse Priority Queue)

Time Complexity: O(n log k), for managing k elements per query.
Space Complexity: O(k), maintaining the heap of k elements.

Priority Queue (Max-Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Min-Heap storing all distancesO(n log n)O(n)Simple implementation when constraints are small and storing all distances is acceptable
Max-Heap of size kO(n log k)O(k)Best for streaming queries and large inputs where only the k closest obstacles matter

Video Solution

K-th Nearest Obstacle Queries || LeetCode Weekly Contest 413 || Leetcode Solution • codi • 938 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is K-th Nearest Obstacle Queries easy or hard?
K-th Nearest Obstacle Queries is generally rated Medium. The logic becomes straightforward once you recognize the pattern of maintaining the k-th smallest value in a stream using a bounded heap.
K-th Nearest Obstacle Queries Python/Java solution
Python typically uses the heapq module with negated values to simulate a max-heap. Java implementations use PriorityQueue with a custom comparator to maintain the largest distance at the top. Both implementations maintain a heap of size k and update the result after each query.
How to solve K-th Nearest Obstacle Queries in O(n log k)?
Maintain a max-heap that stores the k smallest obstacle distances encountered so far. For each query, compute the distance and insert it into the heap. If the heap size exceeds k, remove the maximum element. After processing a query, return the heap's top if size is k; otherwise return -1.
What is the best approach for K-th Nearest Obstacle Queries?
The optimal approach uses a max-heap (priority queue) limited to size k. For every query, compute the obstacle's distance to the origin and push it into the heap. If the heap grows larger than k, remove the largest distance. The heap's top element becomes the current k-th nearest obstacle, giving O(n log k) time and O(k) space.
Is K-th Nearest Obstacle Queries asked at Google/Amazon/Meta?
Variations of this problem appear in interviews that test streaming data processing and top-k maintenance. Companies such as Amazon, Google, and Meta commonly ask heap-based questions where you maintain the k-th smallest or largest element while processing incoming data.
What data structure is used in K-th Nearest Obstacle Queries?
The key data structure is a heap, implemented as a priority queue. A max-heap of size k efficiently tracks the k closest obstacle distances, allowing quick insertion and removal while keeping the k-th nearest value accessible at the top.
What is the time complexity of K-th Nearest Obstacle Queries?
Using the optimal heap strategy, each query performs at most one insertion and one removal from a heap of size k. Each heap operation costs O(log k), so processing n queries takes O(n log k) time. The space complexity is O(k) because only the k closest distances are stored.

Ready to solve this problem?

Practice K-th Nearest Obstacle Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

K Closest Points to Origin