Problem Description

You are given an infinite 2D plane with no obstacles initially. Given a positive integer k and a list of queries queries, you will build obstacles sequentially at specific coordinates. Each query will provide coordinates [x, y] for an obstacle, and no coordinate will be repeated. For each query, you need to determine the distance to the kth closest obstacle from the origin (0, 0). If there are fewer than k obstacles after a query, return -1 for that query. The distance of an obstacle from the origin is calculated as |x| + |y|.

Intuition

The problem requires tracking distances of obstacles from the origin and maintaining an ordered list of these distances to efficiently find the kth smallest value after each insertion. For this, a max-heap is suitable since it allows us to keep the smallest k distances while discarding larger ones.

Here's the step-by-step breakdown of the solution:

1. Initialize a Max-Heap: Use a max-heap to store obstacle distances in a way that always leaves the largest of the k smallest distances at the top. This allows easy replacement as new obstacles are added.

2. Iterate Over Queries: For each query in queries, calculate the Manhattan distance of the obstacle (x, y) from the origin.

3. Manage Heap Size: Add the calculated distance to the max-heap. If the size of the heap exceeds k, remove the top element, which is the largest among the k+1 smallest distances.

4. Construct the Result: After processing each query, if the heap has at least k elements, the obstacle distance at the top represents the kth closest distance from the origin. Otherwise, append -1 to the result list indicating insufficient obstacles.

By following this process for each query, the algorithm efficiently determines and manages the kth nearest distance dynamically.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution employs a priority queue, specifically a max-heap, to efficiently track and retrieve the kth nearest obstacle distance after each query.

Implementation Steps:

1. Initialize a Max-Heap: Use Python's heapq library which by default provides a min-heap. To simulate a max-heap, store negative distances.

2. Iterate Through Queries:

   • For each obstacle coordinate (x, y) in queries, calculate its distance from the origin using the formula distance = |x| + |y|.
   • Push this distance as a negative value into the heap using heappush.

3. Maintain Heap Size:

   • If the heap size exceeds k, pop the largest element using heappop to ensure only the k smallest distances remain actively managed.
   • For efficiency, ensure only k elements are stored in the heap at any point after processing a sufficient number of queries.

4. Build the Result Array:

   • For each query processed, if the number of obstacles (i.e., the size of the heap) is at least k, append the top of the heap to the result list (flipping the sign back to positive).
   • If fewer than k obstacles are present, append -1.

By leveraging the max-heap, this approach efficiently handles updates with each query and dynamically retrieves the kth closest distance without needing to sort all obstacle distances repeatedly. The complexity primarily revolves around heap operations, making this method both effective and scalable for large sets of queries.

Example Walkthrough

Let's consider an example to understand the solution approach for determining the kth closest obstacle distance.

Suppose we have k = 2 and queries = [[3, 2], [1, 4], [0, 6], [2, 3]].

To solve this, we will use a max-heap to keep track of the smallest k distances.

1. Initialize the Max-Heap: Start with an empty heap.

2. Process Each Query:

   • Query 1: Obstacle at [3, 2]

     • Calculate the Manhattan distance: |3| + |2| = 5.
     • Add -5 to the heap to simulate a max-heap.
     • Heap status: [-5]
     • Since we have fewer than k distances, append -1 to the result.

   • Query 2: Obstacle at [1, 4]

     • Calculate the Manhattan distance: |1| + |4| = 5.
     • Add -5 to the heap.
     • Heap status: [-5, -5]
     • We now have k distances, so append 5 (flip sign) to the result.

   • Query 3: Obstacle at [0, 6]

     • Calculate the Manhattan distance: |0| + |6| = 6.
     • Add -6 to the heap.
     • Heap status: [-6, -5, -5]
     • Since the heap exceeds k, remove the largest: -6.
     • Remaining heap: [-5, -5]
     • Append 5 to the result.

   • Query 4: Obstacle at [2, 3]

     • Calculate the Manhattan distance: |2| + |3| = 5.
     • Add -5 to the heap.
     • Heap status: [-5, -5, -5]
     • Remove the largest: -5.
     • Remaining heap: [-5, -5]
     • Append 5 to the result.

Final Result: [-1, 5, 5, 5]

This example demonstrates how using a max-heap helps efficiently manage the nearest distances, illuminating the kth nearest obstacle distance after each query.

Solution Implementation

Time and Space Complexity

The time complexity is O(n \times \log k) because for each query in queries, the procedure heappush and potentially heappop operations are involved. Each of these heap operations takes O(\log k) time since the heap size is maintained at most k. This results in processing n queries leading to a total time complexity of O(n \times \log k).

The space complexity is O(k) since at any point in time, the priority queue pq holds no more than k elements. This is ensured by removing the smallest (in the context of max heap, most negative) element whenever the size of pq surpasses k. Therefore, the maximum space usage by the heap is O(k).

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