2503. Maximum Number of Points From Grid Queries - Detailed Explanation

Problem Statement

You are given an m × n integer matrix grid and an integer array queries of length k. Compute an answer array answer of length k where, for each query value q = queries[i], you start at the top‑left cell (0,0) and repeatedly:

• If q is strictly greater than the value of your current cell (say v), you earn 1 point (but only the first time you visit that cell), and you may move to any of its 4 neighbors (up/down/left/right).
• Otherwise, you stop and cannot earn more points.

Return answer, where answer[i] is the maximum points you can collect for queries[i]. You are allowed to revisit cells (but won’t gain points again), and each query is independent. citeturn0search1

Examples

Input  
  grid    = [[1,2,3],
             [2,5,7],
             [3,5,1]]
  queries = [5,6,2]
Output [5,8,1]
Explanation  
- q=5: you can visit all cells with value<5 reachable from (0,0):  
  cells {1,2,2,3,3} → 5 points.  
- q=6: you can also visit the two “5” cells → +2 = 7,  
  then stop before 7; but you can re‑enter 1 at bottom‑right? No new points.  
  Total = 8.  
- q=2: you stop immediately at (0,0)? 1<2 so get 1 point, but neighbors {2,2} are not <2. → 1  

Constraints

• 1 ≤ m, n ≤ 10^5 with m·n ≤ 10^5
• 1 ≤ grid[i][j], queries[i] ≤ 10^9
• 1 ≤ k ≤ 10^5

Hints

1. A naive per‑query BFS/DFS is O(k·mn) and too slow.
2. Sort your queries in ascending order, and process them incrementally so that you never revisit cells you’ve already “unlocked.”
3. You can use either a priority‑queue BFS (min‑heap by cell value) or a union‑find on all cells sorted by value to maintain a growing region of accessible cells from (0,0).

Approach 1 – Priority‑Queue BFS Across Queries

Idea

Maintain a min‑heap of frontier cells sorted by their grid value. As you raise your threshold (query value), you pop and “unlock” all cells whose value is less than that threshold. Each cell, the first time you unlock it, increments your point count and pushes its 4 neighbors onto the heap. Because queries are sorted, you only ever push each cell once.

Steps

1. Pair each query with its index and sort:

   Q = sorted([(queries[i], i) for i in range(k)])
   

2. Initialize a boolean visited[m][n] = {false}, a min‑heap heap = [(grid[0][0],0,0)], and visited[0][0]=false (we mark when popped). Set count = 0.
3. For each (threshold, qi) in Q (in increasing threshold):
   • While heap not empty and heap[0].value < threshold:
     1. Pop (val, x, y).
     2. If already visited[x][y], continue.
     3. Mark visited[x][y]=true, count++.
     4. For each neighbor (nx,ny) in 4 directions inside bounds and not yet visited, push (grid[nx][ny], nx, ny) onto heap.
   • Set answer[qi] = count.
4. Return answer.

Complexity

• Sorting queries: O(k log k)
• Each cell pushed/popped at most once: O(mn log (mn))
• Total: O((mn + k) log (mn)).

Python Code