Maximum Number of Points From Grid Queries — LeetCode 2503 Python Solution

The 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.

Example

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.

Python solution

class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        m, n = len(grid), len(grid[0])
        qs = sorted((v, i) for i, v in enumerate(queries))
        ans = [0] * len(qs)
        q = [(grid[0][0], 0, 0)]
        cnt = 0
        vis = [[False] * n for _ in range(m)]
        vis[0][0] = True
        for v, k in qs:
            while q and q[0][0] < v:
                _, i, j = heappop(q)
                cnt += 1
                for a, b in pairwise((-1, 0, 1, 0, -1)):
                    x, y = i + a, j + b
                    if 0 <= x < m and 0 <= y < n and not vis[x][y]:
                        heappush(q, (grid[x][y], x, y))
                        vis[x][y] = True
            ans[k] = cnt
        return ans

Complexity

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2503. Maximum Number of Points From Grid Queries is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Related problems