Maximum Number of Points From Grid Queries

Hard Graphs Matrix Graphs Original on LeetCode

Reported atUber

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

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(k · m · n)Each of the k queries may run a BFS over the whole grid.
SpaceO(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.

  1. For each query q: if grid[0][0] >= q, the answer is 0.
  2. Otherwise BFS from (0, 0), entering only unvisited neighbours with value < q.
  3. 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;
    }
}

2Optimal (sorted queries + min-heap frontier)

TimeO(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.
SpaceO(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.

  1. Sort the query indices by query value.
  2. Push (grid[0][0], 0, 0) into a min-heap and mark (0, 0) as seen; count = 0.
  3. 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).
  4. 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;
    }
}

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.