diff options
author | Jack Sangdahl <[email protected]> | 2025-03-27 23:25:48 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-27 23:25:48 -0600 |
commit | 548edd9d34e4c396b8cbb01583bb49ff74b90ed6 (patch) | |
tree | 4e6271aa303f162a7936bbd795f1020c3e55fe51 /max_num_point_grid_query.py | |
parent | 3b7e5a469d82048dbb0122dd2207390ef8f5f653 (diff) | |
download | leetcode-548edd9d34e4c396b8cbb01583bb49ff74b90ed6.tar.gz leetcode-548edd9d34e4c396b8cbb01583bb49ff74b90ed6.zip |
2503. maximum number of points from grid queries
Diffstat (limited to 'max_num_point_grid_query.py')
-rw-r--r-- | max_num_point_grid_query.py | 49 |
1 files changed, 49 insertions, 0 deletions
diff --git a/max_num_point_grid_query.py b/max_num_point_grid_query.py new file mode 100644 index 0000000..642a2ec --- /dev/null +++ b/max_num_point_grid_query.py @@ -0,0 +1,49 @@ +# 2503. Maximum Number of Points From Grid Queries +import heapq +from bisect import bisect_left + +""" +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]' 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 that cell, and you can move to any adjacent cell in all 4 +directions, otherwise you do not get any points, and you end this process. +after the process 'answer[i]' is the maximum number of ponts you can get. +note that for each query, yu are allowed to visit the same cell multiple +times. +""" + + +class Solution(object): + def maxPoints(self, grid, queries): + """ + :type grid: List[List[int]] + :type queries: List[int] + :rtype: List[int] + """ + n, m = len(grid), len(grid[0]) + heap = [(grid[0][0], 0, 0)] + v, order = {(0, 0)}, [] + while len(heap) > 0: + curr, i, j = heapq.heappop(heap) + order.append(curr) + for x, y in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]: + if 0 <= x < n and 0 <= y < m and (x, y) not in v: + v.add((x, y)) + heapq.heappush(heap, (grid[x][y], x, y)) + high = -1 + for i in range(len(order)): + high = max(high, order[i]) + order[i] = high + ans = [] + for i in queries: + ans.append(bisect_left(order, i)) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxPoints(grid=[[1, 2, 3], [2, 5, 7], [3, 5, 1]], queries=[5, 6, 2])) + print(obj.maxPoints(grid=[[5, 2, 1], [1, 1, 2]], queries=[3])) |