⚡Flashcard Drill➔
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

  1. Process the queries offline in increasing order, activating grid cells as the threshold rises.
  2. Union-find over the active cells tracks the size of the component containing the top-left cell.
  3. For a query q, activate every cell with grid value < q; the answer is the size of the top-left cell's component (or 0 if it is not active).
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems