2503. Maximum-Number-Of-Points-From-Grid-Queries

The question gives us a 2D matrix and an array of queries. For each query, we basically want to find the sum of the elements we can access in the grid using the following rules:

• we start from the top left cell
• we move in any direction
• we can only move to a cell if the value is strictly smaller than queries[i]

With these restraints, we can see that this is simply a graph traversal problem. We consider elements that are next to each other in the grid AND have a value smaller than the query value to be adjacent. Then we can simply run DFS or BFS starting from the top left cell and keep track of the total value of the cells we visit.

Obviously, I got the question wrong and it is not the most efficient algorithm. After viewing Hint 1 and Hint 2, I realized that you can consider all queries simultaneously instead of traversing the graph for each query. We can first sort the queries in increasing order while keeping track of their index in the original list. Then we keep track of the current adjacent nodes using a min heap which allows us to see the smallest value in the adjacent nodes. This allows us to iterate through the grid with all queries at once (as all the cells that smaller queries can access are also accessible by larger queries).

We access and sum up all the adjacent nodes that are smaller than the current query value. We keep track of the total sum of the cells we visited and update the result array with the total sum when there are no more cells to visit for that query. Then we move on to the next query and repeat the process, keeping our total sum of visited cells (as any cells visited by the smaller queries will also be visited by the larger ones).

After we go through all the queries, we can return the resulting array.

class Solution(object):
    def maxPoints(self, grid, queries):
        """
        :type grid: List[List[int]]
        :type queries: List[int]
        :rtype: List[int]
        """
        n = len(queries)
        row_n = len(grid)
        col_n = len(grid[0])
        movement = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        queries_pos = [(queries[i], i) for i in range(n)]
        queries_pos.sort()
        res = [0] * n

        total = 0

        visited = [[False] * len(grid[0]) for _ in range(len(grid))]
        min_heap = []

        heapq.heappush(min_heap, (grid[0][0], 0, 0))
        visited[0][0] = True

        print(min_heap)

        for query, index in queries_pos:
            while len(min_heap) != 0 and min_heap[0][0] < query:
                value, row, col = heapq.heappop(min_heap)
                total += 1

                for dy, dx in movement:
                    new_row = row + dy
                    new_col = col + dx

                    if new_row >= 0 and new_col >= 0 and new_row < row_n and new_col < col_n and not visited[new_row][new_col]:
                        heapq.heappush(min_heap, (grid[new_row][new_col], new_row, new_col))
                        visited[new_row][new_col] = True
            res[index] = total

        return res

Time Complexity: O(n * m * log(n * m) + k log(n * m))

Space Complexity: O(n * m)