Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3495. K-th Nearest Obstacle Queries

My accepted Python solution to LeetCode problem 3495, K-th Nearest Obstacle Queries, running in 194ms.

  • Difficulty: Medium
  • Python
  • Runtime 194ms
  • Memory 90.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 194ms, memory 90.5MB, accepted 2025-12-31.

python
class Solution:
    def resultsArray(self, queries: List[List[int]], k: int) -> List[int]:
        import heapq
        result = []
        max_heap = []  # max heap (using negative values)
        
        for x, y in queries:
            dist = abs(x) + abs(y)  # Manhattan distance
            
            if len(max_heap) < k:
                heapq.heappush(max_heap, -dist)
            elif dist < -max_heap[0]:
                heapq.heapreplace(max_heap, -dist)
            
            if len(max_heap) < k:
                result.append(-1)
            else:
                result.append(-max_heap[0])
        
        return result

Source