Maximum Number of Points From Grid Queries
Problem
You are given an m × n matrix grid and an array queries. For each query you start at the top-left cell and may move to any of the 4 adjacent cells as long as the query value is strictly greater than the value of the cell you stand on; each distinct cell visited this way scores one point. Return, for each query, the maximum points obtainable. Cells may be re-visited but only count once.
grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2][5,8,1]import heapq
def maxPoints(grid, queries):
m, n = len(grid), len(grid[0])
ans = [0] * len(queries)
# Answer queries from smallest to largest threshold.
order = sorted(range(len(queries)), key=lambda i: queries[i])
# Min-heap frontier ordered by cell value; start at the corner.
heap = [(grid[0][0], 0, 0)]
seen = [[False] * n for _ in range(m)]
seen[0][0] = True
points = 0
for qi in order:
q = queries[qi]
# Collect every reachable cell strictly below this threshold.
while heap and heap[0][0] < q:
val, r, c = heapq.heappop(heap)
points += 1
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc]:
seen[nr][nc] = True
heapq.heappush(heap, (grid[nr][nc], nr, nc))
ans[qi] = points
return ans// Tiny binary min-heap keyed by element[0] (cell value).
function pushMin(h, x) {
h.push(x);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (h[p][0] <= h[i][0]) break;
[h[p], h[i]] = [h[i], h[p]]; i = p;
}
}
function popMin(h) {
const top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
let i = 0;
for (;;) {
let s = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < h.length && h[l][0] < h[s][0]) s = l;
if (r < h.length && h[r][0] < h[s][0]) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]]; i = s;
}
}
return top;
}
function maxPoints(grid, queries) {
const m = grid.length, n = grid[0].length;
const ans = new Array(queries.length).fill(0);
// Answer queries from smallest to largest threshold.
const order = [...queries.keys()].sort((a, b) => queries[a] - queries[b]);
// Min-heap frontier ordered by cell value; start at the corner.
const heap = [[grid[0][0], 0, 0]];
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
seen[0][0] = true;
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let points = 0;
for (const qi of order) {
const q = queries[qi];
// Collect every reachable cell strictly below this threshold.
while (heap.length && heap[0][0] < q) {
const [val, r, c] = popMin(heap);
points++;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]) {
seen[nr][nc] = true;
pushMin(heap, [grid[nr][nc], nr, nc]);
}
}
}
ans[qi] = points;
}
return ans;
}int[] maxPoints(int[][] grid, int[] queries) {
int m = grid.length, n = grid[0].length, k = queries.length;
int[] ans = new int[k];
// Answer queries from smallest to largest threshold.
Integer[] order = new Integer[k];
for (int i = 0; i < k; i++) order[i] = i;
Arrays.sort(order, (a, b) -> queries[a] - queries[b]);
// Min-heap frontier ordered by cell value; start at the corner.
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
boolean[][] seen = new boolean[m][n];
heap.offer(new int[]{grid[0][0], 0, 0});
seen[0][0] = true;
int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
int points = 0;
for (int qi : order) {
int q = queries[qi];
// Collect every reachable cell strictly below this threshold.
while (!heap.isEmpty() && heap.peek()[0] < q) {
int[] cell = heap.poll();
points++;
for (int t = 0; t < 4; t++) {
int nr = cell[1] + dr[t], nc = cell[2] + dc[t];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]) {
seen[nr][nc] = true;
heap.offer(new int[]{grid[nr][nc], nr, nc});
}
}
}
ans[qi] = points;
}
return ans;
}vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
int m = grid.size(), n = grid[0].size(), k = queries.size();
vector<int> ans(k);
// Answer queries from smallest to largest threshold.
vector<int> order(k);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b){ return queries[a] < queries[b]; });
// Min-heap frontier ordered by cell value; start at the corner.
priority_queue<array<int,3>, vector<array<int,3>>, greater<>> heap;
vector<vector<bool>> seen(m, vector<bool>(n, false));
heap.push({grid[0][0], 0, 0});
seen[0][0] = true;
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
int points = 0;
for (int qi : order) {
int q = queries[qi];
// Collect every reachable cell strictly below this threshold.
while (!heap.empty() && heap.top()[0] < q) {
auto cell = heap.top(); heap.pop();
points++;
for (int t = 0; t < 4; t++) {
int nr = cell[1] + dr[t], nc = cell[2] + dc[t];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]) {
seen[nr][nc] = true;
heap.push({grid[nr][nc], nr, nc});
}
}
}
ans[qi] = points;
}
return ans;
}Explanation
The key insight is that the queries are all known up front, so we can answer them offline in any order we like. A larger threshold unlocks a superset of the cells a smaller threshold unlocks, so if we process queries from smallest to largest we never have to undo any work — the set of collected cells only grows.
Starting from the top-left corner we run a single growing BFS, but instead of a plain FIFO queue we use a min-heap keyed by cell value. The heap always hands back the smallest-value frontier cell next. This is the same idea as Dijkstra: we expand the cheapest boundary first, so a cell is "collected" exactly when the threshold first exceeds its value.
For each query q (in sorted order) we pop every frontier cell whose value is strictly less than q, score a point for it, and push its unvisited neighbors onto the heap. When the heap's smallest value is no longer below q, we stop — the running points counter is the answer for that query. Because we kept the original index in order, we write the answer back to the correct slot.
The corner itself only scores if its own value is below the query: if grid[0][0] >= q the very first pop never fires and the answer is 0, which is exactly Example 2.
Each cell enters and leaves the heap at most once across all queries combined, so the heap work is shared — that is what makes the whole thing efficient.