aboutsummaryrefslogtreecommitdiff
path: root/max_num_point_grid_query.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-27 23:25:48 -0600
committerJack Sangdahl <[email protected]>2025-03-27 23:25:48 -0600
commit548edd9d34e4c396b8cbb01583bb49ff74b90ed6 (patch)
tree4e6271aa303f162a7936bbd795f1020c3e55fe51 /max_num_point_grid_query.py
parent3b7e5a469d82048dbb0122dd2207390ef8f5f653 (diff)
downloadleetcode-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.py49
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]))