Maximum Number of Points From Grid Queries

Hard
1430.

Maximum Number of Points From Grid Queries

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.

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.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 10^5
  • 1 <= queries.length <= 10^4
  • 1 <= grid[i][j], queries[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number[]} queries
 * @return {number[]}
 */
var maxPoints = function(grid, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 10^5
  • 1 <= queries.length <= 10^4
  • 1 <= grid[i][j], queries[i] <= 10^6

Hints for Maximum Number of Points From Grid Queries

  1. 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.

  2. Hint 2

    A larger query reaches everything a smaller one reaches. Answer the queries in increasing order and keep growing one region.

  3. 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

  1. Sort the query indices by query value.
  2. Push the start cell into a min-heap keyed by cell value and mark it seen; set count = 0.
  3. For each query q in increasing order: while the heap's smallest value is < q, pop that cell, increment count, and push every unseen in-bounds neighbour (marking it seen).
  4. Record count as 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 q blocks 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 ans

Java

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