NeetCode #617LC-2503HardGraphs
← Back to All Problems#617 · #2503 · Maximum Number of Points From Grid Queries(矩阵查询可获得的最大分数)
📌 Problem Statement & Constraints
You are given an
m x n grid and queries. For each query q, start at the top-left and repeatedly move to an adjacent cell with a value strictly less than q, collecting points equal to the number of cells visited (the start counts). Return the answer for each query. Constraints: 1 <= m, n <= 1000, 1 <= queries.length <= 10^4, 1 <= grid[i][j], queries[i] <= 10^6.💡 Core Algorithmic Approaches
- Process the queries offline in increasing order, activating grid cells as the threshold rises.
- Union-find over the active cells tracks the size of the component containing the top-left cell.
- For a query
q, activate every cell withgrid value < q; the answer is the size of the top-left cell's component (or 0 if it is not active). - Sorting both the cells and the queries makes the whole thing near-linear.
💻 Benchmark Python3 Implementation
class Solution:
def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
m, n = len(grid), len(grid[0])
cells = sorted((grid[i][j], i, j) for i in range(m) for j in range(n))
order = sorted(range(len(queries)), key=lambda i: queries[i])
parent = list(range(m * n))
size = [1] * (m * n)
active = [False] * (m * n)
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
res = [0] * len(queries)
p = 0
for qi in order:
q = queries[qi]
# activate every cell with value strictly less than q
while p < len(cells) and cells[p][0] < q:
_, i, j = cells[p]
idx = i * n + j
active[idx] = True
for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and active[ni * n + nj]:
ra, rb = find(idx), find(ni * n + nj)
if ra != rb:
parent[ra] = rb
size[rb] += size[ra]
p += 1
if active[0]:
res[qi] = size[find(0)]
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O((m*n + q) log(m*n)): the sorts dominate; each cell is activated once.
💾 Space Complexity
O(m * n + q) for the union-find and the results.
⚠️ Interview Pitfalls & Follow-ups
- Running a BFS per query: O(q * m * n).
- Using
<=when activating cells: the condition is strictly less than the query value. - Forgetting that the start cell may be inactive: the answer is then 0.
- Sorting only the queries: the cells must also be processed in value order.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.