Maximum Number of Points From Grid Queries — Solution
Maximum Number of Points From Grid Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Number of Points From Grid Queries is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Matrix, Breadth-First Search, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n matrix grid of positive integers and an array queries.
Each query q is played separately, starting at the top-left cell. While standing on a cell: if q is strictly greater than the cell's value, you score one point if this is your first time on that cell, and you may step to any of its four neighbours. Otherwise you score nothing there and cannot move on from it.
For every query, return the maximum number of points you can collect — the number of distinct cells you can stand on with a value smaller than q, moving only through such cells. If the top-left value is at least q, the answer is 0.
Example 1
Input: grid = [[2,4,1],[3,5,6],[9,1,2]], queries = [4,6,1,10]
Output: [2,7,0,9]
Explanation: With q = 4 only the cells 2 and 3 are reachable; with q = 6 every cell except 6 and 9 is; q = 1 cannot even leave the start.
Example 2
Input: grid = [[5,2,1],[1,1,2]], queries = [3]
Output: [0]
Explanation: The start holds 5, which is not smaller than 3.
Constraints
m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 10^51 <= queries.length <= 10^41 <= grid[i][j], queries[i] <= 10^6
Hints for Maximum Number of Points From Grid Queries
Hint 1
For one query the answer is the size of the region connected to the start through cells smaller than
q— but a BFS per query is too slow.Hint 2
A larger query reaches everything a smaller one reaches. Answer the queries in increasing order and keep growing one region.
Hint 3
Grow the region with a min-heap of frontier cells keyed by value: pop cells while the smallest frontier value is below the current query, counting them and pushing their unseen neighbours.
How to solve Maximum Number of Points From Grid Queries
Sort the queries. The reachable region only grows as q grows, and the cell that joins it next is always the smallest-valued cell on its border — a best-first flood fill driven by a min-heap, paused at each query threshold.
Approach
- Sort the query indices by query value.
- Push the start cell into a min-heap keyed by cell value and mark it seen; set
count = 0. - For each query
qin increasing order: while the heap's smallest value is< q, pop that cell, incrementcount, and push every unseen in-bounds neighbour (marking it seen). - Record
countas the answer for that query's original index.
Why it works
The heap always holds exactly the border of the counted region. A border cell with value < q is reachable for q (its counted neighbour is), and once every border value is >= q the region cannot be extended for q. Popping smallest-first guarantees no cell is counted before it is truly reachable under the current threshold, and later, larger queries simply continue from where the last one stopped.
Complexity
- Time —
O(mn log(mn) + k log k) - Space —
O(mn + k)
Pitfalls
- The comparison is strict: a cell equal to
qblocks the walk. - Mark cells seen when they are pushed, not when popped, or the same cell enters the heap several times.
- Store each answer at the query's original position; the processing order is sorted.
Reference solution
Python
from typing import List
import heapq
def maxPoints(grid: List[List[int]], queries: List[int]) -> List[int]:
m, n = len(grid), len(grid[0])
order = sorted(range(len(queries)), key=lambda j: queries[j])
ans = [0] * len(queries)
seen = [[False] * n for _ in range(m)]
seen[0][0] = True
heap = [(grid[0][0], 0, 0)] # the region's border, smallest value first
count = 0
for j in order:
q = queries[j]
while heap and heap[0][0] < q:
_, r, c = heapq.heappop(heap)
count += 1
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
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[j] = count
return ansJava
public static int[] maxPoints(int[][] grid, int[] queries) {
int m = grid.length, n = grid[0].length;
Integer[] order = new Integer[queries.length];
for (int j = 0; j < queries.length; j++) order[j] = j;
Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b]));
boolean[][] seen = new boolean[m][n];
seen[0][0] = true;
// the region's border as {value, row, col}, smallest value first
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
heap.add(new int[] { grid[0][0], 0, 0 });
int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
int[] ans = new int[queries.length];
int count = 0;
for (int j : order) {
int q = queries[j];
while (!heap.isEmpty() && heap.peek()[0] < q) {
int[] cur = heap.poll();
count++;
for (int d = 0; d < 4; d++) {
int nr = cur[1] + dr[d], nc = cur[2] + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) continue;
seen[nr][nc] = true;
heap.add(new int[] { grid[nr][nc], nr, nc });
}
}
ans[j] = count;
}
return ans;
}C++
vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
int m = grid.size(), n = grid[0].size();
vector<int> order(queries.size());
for (int j = 0; j < (int) queries.size(); j++) order[j] = j;
sort(order.begin(), order.end(), [&](int a, int b) { return queries[a] < queries[b]; });
vector<vector<bool>> seen(m, vector<bool>(n, false));
seen[0][0] = true;
// the region's border as (value, cell), smallest value first
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
heap.push({grid[0][0], 0});
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
vector<int> ans(queries.size(), 0);
int count = 0;
for (int j : order) {
int q = queries[j];
while (!heap.empty() && heap.top().first < q) {
int cell = heap.top().second;
heap.pop();
count++;
int r = cell / n, c = cell % n;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) continue;
seen[nr][nc] = true;
heap.push({grid[nr][nc], nr * n + nc});
}
}
ans[j] = count;
}
return ans;
}JavaScript
var maxPoints = function(grid, queries) {
var m = grid.length, n = grid[0].length;
var SHIFT = 131072; // 2^17 > m * n: a key is value * SHIFT + cell
var order = [];
for (var j = 0; j < queries.length; j++) order.push(j);
order.sort(function(a, b) { return queries[a] - queries[b]; });
var seen = [];
for (var c = 0; c < m * n; c++) seen.push(false);
seen[0] = true;
var heap = [grid[0][0] * SHIFT]; // the region's border, smallest value first
var ans = [];
for (var z = 0; z < queries.length; z++) ans.push(0);
var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
var count = 0;
for (var t = 0; t < order.length; t++) {
var q = queries[order[t]];
while (heap.length > 0 && Math.floor(heap[0] / SHIFT) < q) {
var cell = heapPop(heap) % SHIFT;
count++;
var row = Math.floor(cell / n), col = cell % n;
for (var d = 0; d < 4; d++) {
var nr = row + dr[d], nc = col + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
var id = nr * n + nc;
if (seen[id]) continue;
seen[id] = true;
heapPush(heap, grid[nr][nc] * SHIFT + id);
}
}
ans[order[t]] = count;
}
return ans;
};
var heapPush = function(h, v) {
h.push(v);
var i = h.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (h[p] <= h[i]) break;
var t = h[p]; h[p] = h[i]; h[i] = t;
i = p;
}
};
var heapPop = function(h) {
var top = h[0];
var last = h.pop();
if (h.length > 0) {
h[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === j) break;
var t = h[s]; h[s] = h[j]; h[j] = t;
j = s;
}
}
return top;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal