Problem Description

You have an infinite 2D plane where you'll be placing obstacles one by one. Given a positive integer k and a 2D array queries, you need to track the k-th nearest obstacle to the origin after each placement.

Each query queries[i] = [x, y] represents placing an obstacle at coordinate (x, y). The distance from any obstacle to the origin is calculated using Manhattan distance: |x| + |y|.

After placing each obstacle, you need to determine:

• If there are at least k obstacles on the plane, find the distance of the k-th nearest obstacle from the origin
• If there are fewer than k obstacles, return -1

The function should return an array results where results[i] contains the k-th nearest obstacle distance after processing the i-th query.

Example walkthrough:

• If k = 2 and queries are [[1,2], [3,4], [2,3]]
• After 1st query: Only 1 obstacle at (1,2) with distance 3. Since we need 2 obstacles, return -1
• After 2nd query: 2 obstacles with distances 3 and 7. The 2nd nearest has distance 7
• After 3rd query: 3 obstacles with distances 3, 5, and 7. The 2nd nearest has distance 5

The solution uses a max-heap of size k to efficiently track the k nearest obstacles. As new obstacles are added, if the heap exceeds size k, the farthest obstacle (top of max-heap) is removed, ensuring the heap always contains the k nearest obstacles.

Intuition

The key insight is recognizing that we need to efficiently maintain and query the k-th smallest distance as we add obstacles one by one.

When we think about finding the k-th smallest element in a dynamic dataset (where elements are continuously added), a heap data structure naturally comes to mind. But which type of heap should we use?

If we used a min-heap to store all obstacles, we'd need to extract elements k times to find the k-th nearest, which would be inefficient for repeated queries. Instead, we can flip our perspective: rather than tracking all obstacles and finding the k-th smallest, we can maintain only the k nearest obstacles at any time.

This leads us to use a max-heap with a size limit of k. Here's why this works beautifully:

• The max-heap stores at most k elements (the k nearest obstacles)
• The root of the max-heap is always the largest among these k elements, which is exactly the k-th nearest obstacle
• When a new obstacle comes in, we add it to the heap
• If the heap size exceeds k, we remove the largest element (the farthest among the k+1 obstacles)
• This ensures we always keep exactly the k nearest obstacles

The elegance of this approach is that we get O(1) access to the k-th nearest distance (it's always at the root), and we only need O(log k) time to process each new obstacle, regardless of how many total obstacles we've placed.

Since Python's heapq implements a min-heap, we store negative distances to simulate a max-heap behavior - the smallest negative value (most negative) represents the largest positive distance.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution implements a max-heap strategy using Python's heapq module to maintain the k nearest obstacles.

Implementation walkthrough:

1. Initialize data structures:

   • ans = []: Stores the result for each query
   • pq = []: Priority queue (max-heap) to maintain k nearest obstacles

2. Process each query:

   for i, (x, y) in enumerate(queries):

   We iterate through each obstacle placement with its index.

3. Calculate distance and add to heap:

   heappush(pq, -(abs(x) + abs(y)))

   • Calculate Manhattan distance: |x| + |y|
   • Push the negative of the distance to simulate max-heap behavior (since Python's heapq is a min-heap)
   • The most negative value (smallest in min-heap) represents the largest positive distance

4. Maintain heap size:

   if i >= k:
       heappop(pq)

   • Once we have more than k obstacles (when i >= k), remove the largest distance
   • This keeps exactly k nearest obstacles in the heap

5. Determine the k-th nearest distance:

   ans.append(-pq[0] if i >= k - 1 else -1)

   • If we have at least k obstacles (i >= k - 1), the root of the max-heap contains the k-th nearest distance
   • Convert back to positive by negating: -pq[0]
   • Otherwise, append -1 as we don't have enough obstacles yet

Time Complexity: O(n log k) where n is the number of queries

• Each insertion: O(log k)
• Each deletion: O(log k)
• Getting the k-th element: O(1)

Space Complexity: O(k) for the heap storage

Example Walkthrough

Let's walk through a concrete example with k = 3 and queries = [[5,5], [4,4], [3,3], [2,2], [1,1]].

We'll maintain a max-heap (using negative values) that stores at most 3 distances.

Initial state:

• ans = []
• pq = [] (empty heap)

Query 0: [5,5]

• Distance = |5| + |5| = 10
• Push -10 to heap: pq = [-10]
• Check: i=0, k=3, so i < k-1 (0 < 2)
• Not enough obstacles yet, append -1
• ans = [-1]

Query 1: [4,4]

• Distance = |4| + |4| = 8
• Push -8 to heap: pq = [-8, -10] (heap maintains order)
• Check: i=1, k=3, so i < k-1 (1 < 2)
• Still not enough obstacles, append -1
• ans = [-1, -1]

Query 2: [3,3]

• Distance = |3| + |3| = 6
• Push -6 to heap: pq = [-6, -10, -8] (root is -6, the smallest negative = largest positive)
• Check: i=2, k=3, so i = k-1 (2 = 2)
• We have exactly k obstacles! The k-th nearest is -pq[0] = -(-6) = 10
• ans = [-1, -1, 10]

Query 3: [2,2]

• Distance = |2| + |2| = 4
• Push -4 to heap: pq = [-4, -6, -8, -10]
• Check: i=3, k=3, so i >= k (3 >= 3)
• Heap has 4 elements, pop the largest (root): removed -4, pq = [-6, -10, -8]
• The k-th nearest is -pq[0] = -(-6) = 8
• ans = [-1, -1, 10, 8]

Query 4: [1,1]

• Distance = |1| + |1| = 2
• Push -2 to heap: pq = [-2, -6, -8, -10]
• Check: i=4, k=3, so i >= k (4 >= 3)
• Heap has 4 elements, pop the largest (root): removed -2, pq = [-6, -10, -8]
• The k-th nearest is -pq[0] = -(-6) = 6
• ans = [-1, -1, 10, 8, 6]

Key observations:

• The heap always maintains the k smallest distances (as negative values)
• The root of our max-heap (most negative value) represents the k-th smallest distance
• Once we exceed k elements, we remove the largest distance to keep only k nearest obstacles
• The final result shows how the k-th nearest distance decreases as we add closer obstacles: 10 → 8 → 6

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log k), where n is the length of the queries array. This is because:

• The code iterates through all n queries once
• For each query, it performs a heappush operation which takes O(log k) time since the heap size is maintained at most k elements
• When i >= k, a heappop operation is performed which also takes O(log k) time
• Accessing the top element of the heap with pq[0] takes O(1) time

The space complexity is O(k). This is because:

• The heap pq stores at most k elements at any given time (elements are popped when the size exceeds k)
• The answer list ans stores n elements, but this is typically considered as output space and not counted in auxiliary space complexity
• Other variables like i, x, y use O(1) space

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusion with Heap Size Management

A common mistake is incorrectly managing when to pop from the heap. Developers often confuse the condition i >= k with i > k or use len(max_heap) > k instead.

Incorrect approach:

# Wrong: This pops too early
if i > k:
    heapq.heappop(max_heap)

# Or wrong: This doesn't account for 0-based indexing
if len(max_heap) > k:
    heapq.heappop(max_heap)

Why it's wrong: Using i > k means we start popping from the (k+2)th element instead of the (k+1)th element. This keeps k+1 elements in the heap instead of k.

Correct approach:

# Right: Start popping when we have more than k elements
if i >= k:
    heapq.heappop(max_heap)

2. Forgetting to Negate Values for Max-Heap Simulation

Python's heapq only provides min-heap functionality. A common error is forgetting to negate values when pushing or retrieving from the heap.

Incorrect approach:

# Wrong: Treating it as a natural max-heap
heapq.heappush(max_heap, abs(x_coord) + abs(y_coord))
result.append(max_heap[0] if i >= k - 1 else -1)

Why it's wrong: This creates a min-heap, so max_heap[0] would be the smallest distance, not the k-th smallest.

Correct approach:

# Push negative values to simulate max-heap
heapq.heappush(max_heap, -(abs(x_coord) + abs(y_coord)))
# Negate when retrieving to get positive distance
result.append(-max_heap[0] if i >= k - 1 else -1)

3. Off-by-One Error in Result Condition

Determining when we have exactly k elements is tricky due to 0-based indexing.

Incorrect approach:

# Wrong: This waits one query too long
if i >= k:
    result.append(-max_heap[0])
else:
    result.append(-1)

Why it's wrong: When i = k-1, we already have k elements (indices 0 to k-1), but this code would still return -1.

Correct approach:

# Right: We have k elements when index reaches k-1
if i >= k - 1:
    result.append(-max_heap[0])
else:
    result.append(-1)

4. Using Set to Track Duplicates

Some might think duplicate coordinates need special handling and try to use a set.

Incorrect approach:

seen = set()
for x, y in queries:
    if (x, y) not in seen:
        seen.add((x, y))
        heapq.heappush(max_heap, -(abs(x) + abs(y)))

Why it's wrong: The problem asks for the k-th nearest obstacle after each placement. Multiple obstacles at the same location or with the same distance are valid and should all be counted.

Correct approach: Treat each query as a separate obstacle, even if it has the same coordinates or distance as a previous one.