Maximum Number of Points From Grid Queries
Maximum Number of Points From Grid Queries is a hard graphs problem solved with the matrix graphs pattern.
The best approach, optimal (sorted queries + min-heap frontier), runs in O(m·n·log(m·n) + k log k) time and O(m·n + k) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs per query) up.
Problem
You get an m x n integer matrix grid and an integer array queries. Each query is answered on its own, starting from the top-left cell (0, 0) with no points.
For a query value q: if q is strictly greater than the value of the cell you stand on, you score one point the first time you are on that cell and may move to any of its four neighbours. Otherwise you stop. Cells can be revisited, but each scores only once.
Return an array where answer[i] is the most points you can collect for queries[i]. In other words, it is the number of cells reachable from (0, 0) through cells whose values are all strictly less than the query.
Examples
Example 1
- Input
grid = [[2,5],[3,1]], queries = [3,6,1]- Output
[1,4,0]- Why
- For 3 only the start cell (2) is smaller; for 6 every cell is; for 1 even the start cell is too big.
Example 2
- Input
grid = [[1,9,1],[1,9,1],[1,1,1]], queries = [2,10]- Output
[7,9]- Why
- With 2 you walk around the two 9s through all seven 1s; with 10 every cell is open.
Constraints
m == grid.length,n == grid[i].length2 <= m, n <= 1000and4 <= m * n <= 10^51 <= grid[i][j], queries[i] <= 10^61 <= queries.length <= 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (BFS per query) | O(k · m · n) | O(m · n) |
| Optimal (sorted queries + min-heap frontier) | O(m·n·log(m·n) + k log k) | O(m·n + k) |
1Brute force (BFS per query)
O(k · m · n)Each of the k queries may run a BFS over the whole grid.O(m · n)The visited grid and the BFS queue.Answer each query on its own: if the start cell is below the query, BFS from it through cells strictly below the query and count the cells visited.
- For each query q: if grid[0][0] >= q, the answer is 0.
- Otherwise BFS from (0, 0), entering only unvisited neighbours with value < q.
- The answer is the number of cells visited.
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int[] maxPoints(int[][] grid, int[] queries) {
int m = grid.length, n = grid[0].length;
int[] ans = new int[queries.length];
for (int qi = 0; qi < queries.length; qi++) {
int q = queries[qi];
if (grid[0][0] >= q) continue;
boolean[][] seen = new boolean[m][n];
ArrayDeque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] {0, 0});
seen[0][0] = true;
int count = 0;
while (!dq.isEmpty()) {
int[] cur = dq.poll();
count++;
for (int[] d : DIRS) {
int r = cur[0] + d[0], c = cur[1] + d[1];
if (r >= 0 && r < m && c >= 0 && c < n && !seen[r][c] && grid[r][c] < q) {
seen[r][c] = true;
dq.add(new int[] {r, c});
}
}
}
ans[qi] = count;
}
return ans;
}
}class Solution:
def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
m, n = len(grid), len(grid[0])
ans = []
for q in queries:
if grid[0][0] >= q:
ans.append(0)
continue
seen = [[False] * n for _ in range(m)]
seen[0][0] = True
dq = deque([(0, 0)])
count = 0
while dq:
r, c = dq.popleft()
count += 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] and grid[nr][nc] < q:
seen[nr][nc] = True
dq.append((nr, nc))
ans.append(count)
return ansclass Solution {
public:
vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
int m = grid.size(), n = grid[0].size();
const int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
vector<int> ans(queries.size(), 0);
for (size_t qi = 0; qi < queries.size(); qi++) {
int q = queries[qi];
if (grid[0][0] >= q) continue;
vector<vector<bool>> seen(m, vector<bool>(n, false));
queue<pair<int, int>> dq;
dq.push({0, 0});
seen[0][0] = true;
int count = 0;
while (!dq.empty()) {
auto [r, c] = dq.front();
dq.pop();
count++;
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] && grid[nr][nc] < q) {
seen[nr][nc] = true;
dq.push({nr, nc});
}
}
}
ans[qi] = count;
}
return ans;
}
};function maxPoints(grid, queries) {
const m = grid.length, n = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
return queries.map((q) => {
if (grid[0][0] >= q) return 0;
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
seen[0][0] = true;
const dq = [[0, 0]];
for (let h = 0; h < dq.length; h++) {
const [r, c] = dq[h];
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] && grid[nr][nc] < q) {
seen[nr][nc] = true;
dq.push([nr, nc]);
}
}
}
return dq.length;
});
}2Optimal (sorted queries + min-heap frontier)
O(m·n·log(m·n) + k log k)Every cell enters and leaves the heap at most once (log factor each), and the queries are sorted once.O(m·n + k)The heap, the seen grid and the sorted query order.Process the queries from smallest to largest and grow one region instead of restarting. The region's border lives in a min-heap keyed by cell value, starting with (0, 0). For each query, keep popping the smallest border cell while it is below the query: it joins the region, and its unseen neighbours join the border. The region size after that is the query's answer; write it at the query's original index.
- Sort the query indices by query value.
- Push (grid[0][0], 0, 0) into a min-heap and mark (0, 0) as seen; count = 0.
- For each query q in increasing order: while the heap is non-empty and its smallest value < q, pop it, count++, and push every unseen neighbour (marking it seen).
- Store count as the answer for that query's index.
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int[] maxPoints(int[][] grid, int[] queries) {
int m = grid.length, n = grid[0].length, k = queries.length;
Integer[] order = new Integer[k];
for (int i = 0; i < k; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b]));
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
boolean[][] seen = new boolean[m][n];
heap.add(new int[] {grid[0][0], 0, 0});
seen[0][0] = true;
int[] ans = new int[k];
int count = 0;
for (int idx : order) {
int q = queries[idx];
while (!heap.isEmpty() && heap.peek()[0] < q) {
int[] cur = heap.poll();
count++;
for (int[] d : DIRS) {
int r = cur[1] + d[0], c = cur[2] + d[1];
if (r >= 0 && r < m && c >= 0 && c < n && !seen[r][c]) {
seen[r][c] = true;
heap.add(new int[] {grid[r][c], r, c});
}
}
}
ans[idx] = count;
}
return ans;
}
}class Solution:
def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
m, n = len(grid), len(grid[0])
order = sorted(range(len(queries)), key=lambda i: queries[i])
seen = [[False] * n for _ in range(m)]
seen[0][0] = True
heap = [(grid[0][0], 0, 0)]
ans = [0] * len(queries)
count = 0
for idx in order:
q = queries[idx]
while heap and heap[0][0] < q:
_, r, c = heapq.heappop(heap)
count += 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[idx] = count
return ansclass Solution {
public:
vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
int m = grid.size(), n = grid[0].size(), k = queries.size();
const int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
vector<int> order(k);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) { return queries[a] < queries[b]; });
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> heap;
vector<vector<bool>> seen(m, vector<bool>(n, false));
heap.push({grid[0][0], 0, 0});
seen[0][0] = true;
vector<int> ans(k);
int count = 0;
for (int idx : order) {
int q = queries[idx];
while (!heap.empty() && heap.top()[0] < q) {
auto cur = heap.top();
heap.pop();
count++;
for (int d = 0; d < 4; d++) {
int r = cur[1] + DR[d], c = cur[2] + DC[d];
if (r >= 0 && r < m && c >= 0 && c < n && !seen[r][c]) {
seen[r][c] = true;
heap.push({grid[r][c], r, c});
}
}
}
ans[idx] = count;
}
return ans;
}
};function maxPoints(grid, queries) {
const m = grid.length, n = grid[0].length, k = queries.length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const order = [...Array(k).keys()].sort((a, b) => queries[a] - queries[b]);
// binary min-heap of [value, r, c]
const heap = [];
const push = (item) => {
heap.push(item);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p][0] <= heap[i][0]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0], last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let s = i;
if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
if (s === i) break;
[heap[s], heap[i]] = [heap[i], heap[s]];
i = s;
}
}
return top;
};
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
seen[0][0] = true;
push([grid[0][0], 0, 0]);
const ans = new Array(k).fill(0);
let count = 0;
for (const idx of order) {
const q = queries[idx];
while (heap.length > 0 && heap[0][0] < q) {
const [, r, c] = pop();
count++;
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;
push([grid[nr][nc], nr, nc]);
}
}
}
ans[idx] = count;
}
return ans;
}Edge cases to test
- A query not larger than grid[0][0]: the answer is 0
- A query larger than every cell: the answer is m * n
- Equal values: a cell only opens when the query is strictly greater
- Small cells hidden behind a wall of large ones are not reachable
- Repeated and unsorted queries
Hints
Hint 1
For one query the answer is the size of the region reachable from (0, 0) through cells strictly smaller than the query: one BFS.
Hint 2
A bigger query opens a superset of the cells a smaller one opens. Answer the queries in increasing order and keep growing the same region instead of restarting.
Hint 3
Keep the region's border in a min-heap keyed by cell value. For each query, pop and absorb border cells while the smallest one is below the query.
FAQ
What is the best time complexity for Maximum Number of Points From Grid Queries?
Optimal (sorted queries + min-heap frontier) runs in O(m·n·log(m·n) + k log k) time and O(m·n + k) extra space. Every cell enters and leaves the heap at most once (log factor each), and the queries are sorted once.
Which pattern does Maximum Number of Points From Grid Queries use?
It is a graphs problem that uses the matrix graphs pattern. Other problems with the same pattern: Flood Fill, Contain Virus, Number of Distinct Islands.
Is there a brute force solution for Maximum Number of Points From Grid Queries?
Yes. Brute force (BFS per query) takes O(k · m · n) time and O(m · n) space. Answer each query on its own: if the start cell is below the query, BFS from it through cells strictly below the query and count the cells visited.
Which edge cases should I test for Maximum Number of Points From Grid Queries?
A query not larger than grid[0][0]: the answer is 0; A query larger than every cell: the answer is m n; Equal values: a cell only opens when the query is strictly greater; Small cells hidden behind a wall of large ones are not reachable; Repeated and unsorted queries.