Intuition

The problem requires efficiently processing queries to count the number of reachable grid cells with values strictly less than each query value. The key observation is that we can utilize a priority queue (min-heap) to process grid cells in ascending order while maintaining a count of visited cells.

Approach

1. Sorting Queries: Since queries are independent, we first sort them in increasing order, keeping track of their original indices.
2. Min-Heap Processing: We use a min-heap to explore the grid in increasing order of values, always expanding to the smallest neighboring value first.
3. Grid Traversal: Starting from the top-left cell, we use a heap to store the reachable cells in increasing order, marking them visited as we process them.
4. Answering Queries: For each query, we pop cells from the heap while their values are less than the query value and count them.
5. Result Assignment: The count of visited cells is stored at the respective index of each query, preserving the original order.

Complexity

• Time Complexity: O(mn log(mn) + q log q) where m, n are the grid dimensions and q is the number of queries.
• Sorting queries takes O(q log q).
• Each cell is pushed and popped from the heap once, which takes O(mn log(mn)).
• Space Complexity: O(mn + q) due to the grid and query storage.

Code

class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        ROW, COL = len(grid), len(grid[0])
        queries = [(val, idx) for idx, val in enumerate(queries)]
        queries.sort()  # Process queries in increasing order

        heap = []
        heapq.heappush(heap, (grid[0][0], 0, 0))
        grid[0][0] = 0  # Mark as visited

        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        res = [0] * len(queries)
        count = 0

        for val, idx in queries:
            while heap and heap[0][0] < val:
                current_val, i, j = heapq.heappop(heap)
                count += 1

                for di, dj in dirs:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < ROW and 0 <= nj < COL and grid[ni][nj] != 0:
                        heapq.heappush(heap, (grid[ni][nj], ni, nj))
                        grid[ni][nj] = 0  # Mark as visited

            res[idx] = count

        return res