We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K-th Nearest Obstacle Queries

Number: 3495

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an infinite 2D plane and a series of queries that add obstacles at specified coordinates, we must return the Manhattan distance of the k-th nearest obstacle from the origin after each query. The Manhattan distance of a point (x, y) is defined as |x| + |y|. If there are fewer than k obstacles at any point, output -1 for that query.

Key Insights

  • We need to efficiently maintain the k smallest Manhattan distances seen so far.
  • A max-heap of size k is an ideal data structure since its root always contains the current k-th smallest (or the highest among the k smallest) Manhattan distance.
  • For each query:
    • Compute the Manhattan distance.
    • If the heap has fewer than k elements, simply add the new distance.
    • Otherwise, if the new distance is smaller than the maximum (root) of the heap, remove the current maximum and insert the new distance.
  • The root of the heap is the k-th nearest obstacle when the heap size is at least k.

Space and Time Complexity

Time Complexity: O(Q * log k) where Q is the number of queries, since each query does at most O(log k) operations. Space Complexity: O(k) for maintaining the max-heap.

Solution

The approach uses a max-heap (simulated with a min-heap by storing negative values in languages that provide only a min-heap by default like Python) to maintain the k smallest Manhattan distances. For each query, we:

  1. Calculate the Manhattan distance = |x| + |y|.
  2. If the current number of obstacles is less than k, we push the negative of the distance onto the heap.
  3. Otherwise, check if the new distance is smaller than the current k-th smallest (i.e., if it is smaller than -heap[0]). If so, pop the maximum and push the new distance.
  4. Append the current k-th smallest to the results if we have k obstacles; else append -1.

This guarantees that the k-th nearest obstacle is available in the heap’s root after processing each query.

Code Solutions

import heapq

def kthNearestObstacle(queries, k):
    # max_heap will simulate max-heap by pushing negative values
    max_heap = []
    results = []
    
    for x, y in queries:
        # Compute Manhattan distance from the origin
        distance = abs(x) + abs(y)
        
        # If less than k obstacles so far, add the current one
        if len(max_heap) < k:
            heapq.heappush(max_heap, -distance)
        # Else if current distance is smaller than the k-th smallest (largest in heap)
        elif -max_heap[0] > distance:
            heapq.heappop(max_heap)
            heapq.heappush(max_heap, -distance)
        
        # If there are fewer than k obstacles, append -1, else append kth smallest
        if len(max_heap) < k:
            results.append(-1)
        else:
            results.append(-max_heap[0] * -1)
            
    return results

# Example usage
queries = [[1,2],[3,4],[2,3],[-3,0]]
k = 2
print(kthNearestObstacle(queries, k))  # Output: [-1,7,5,3]
← Back to All Questions