Maximum Number of Points From Grid Queries

Problem

You are given an m x n integer matrix grid and an array queries of size k.

Find an array answer of size k such that for each integer queries[i] you start in the top left cell of the matrix and repeat the following process:

• If queries[i] is strictly greater than the value of the current cell that you are in, then you get one point if it is your first time visiting this cell, and you can move to any adjacent cell in all 4 directions: up, down, left, and right.
• Otherwise, you do not get any points, and you end this process.

After the process, answer[i] is the maximum number of points you can get. Note that for each query you are allowed to visit the same cell multiple times.

Return the resulting array answer.

Examples

Example 1:

Input: grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
Output: [5,8,1]
Explanation: The diagrams above show which cells we visit to get points for each query.

Example 2:

Input: grid = [[5,2,1],[1,1,2]], queries = [3]
Output: [0]
Explanation: We can not get any points because the value of the top left cell is already greater than or equal to 3.

Constraints:

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 105
• k == queries.length
• 1 <= k <= 104
• 1 <= grid[i][j], queries[i] <= 106

Solution

Method 1 - Using Binary search + Heap

The problem involves simulating a grid traversal for multiple queries. The task is to determine how many points can be collected starting from the top-left cell of the matrix, given the conditions that the current cell value should be strictly less than a query value for a point to be counted.

• Process the queries in sorted order, as this allows us to incrementally update which cells are accessible.
• Maintain a 2D grid representing visited cells. Use BFS or DFS to explore all cells satisfying the condition for the current query.
• For each query, return the number of reachable points in the matrix.
• Sort queries in ascending order and process them to reduce repeated traversal.
• Use BFS combined with a priority queue to rapidly traverse and update the grid.

Code

Java

class Solution {
    public int[] maxPoints(int[][] grid, int[] queries) {
        int m = grid.length, n = grid[0].length, k = queries.length;
        int[] ans = new int[k];
        
        // Pair queries with their original indices
        int[][] qWithIdx = new int[k][2];
        for (int i = 0; i < k; i++) {
            qWithIdx[i][0] = queries[i];
            qWithIdx[i][1] = i;
        }
        Arrays.sort(qWithIdx, Comparator.comparingInt(a -> a[0]));
        
        // Directions for traversal
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] visited = new boolean[m][n];
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> grid[a[0]][a[1]]));
        pq.offer(new int[]{0, 0});
        visited[0][0] = true;
        int count = 0, lastQuery = Integer.MIN_VALUE;
        
        for (int[] q : qWithIdx) {
            while (!pq.isEmpty() && grid[pq.peek()[0]][pq.peek()[1]] < q[0]) {
                int[] cell = pq.poll();
                count++;
                for (int[] d : dir) {
                    int x = cell[0] + d[0], y = cell[1] + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) {
                        visited[x][y] = true;
                        pq.offer(new int[]{x, y});
                    }
                }
            }
            ans[q[1]] = count;
        }
        return ans;
    }
}

Python

class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        m, n = len(grid), len(grid[0])
        k = len(queries)
        ans: List[int] = [0] * k
        
        # Pair queries with indices and sort by query value
        indexed_queries = sorted((q, i) for i, q in enumerate(queries))
        
        # Directions for traversal
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        visited = [[False] * n for _ in range(m)]
        
        # Priority queue for BFS
        pq = [(grid[0][0], 0, 0)]
        visited[0][0] = True
        count = 0
        
        for query, idx in indexed_queries:
            while pq and pq[0][0] < query:
                _, x, y = heapq.heappop(pq)
                count += 1
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                        heapq.heappush(pq, (grid[nx][ny], nx, ny))
                        visited[nx][ny] = True
            ans[idx] = count
        
        return ans

Complexity

• ⏰ Time complexity: O(k * (m * n)) in the worst-case scenario, where k is the number of queries, m is the number of rows, and n is the number of columns.
• 🧺 Space complexity:  O(m * n) to track visited cells and store intermediate grids.