# Maximum Number of Points From Grid Queries
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-points-from-grid-queries)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-points-from-grid-queries
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Heap (Priority Queue), Matrix
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
You are given an `m x n` integer matrix `grid` and an array `queries` of size `k`.

Find an array `answer` of size `k` such that for each integer `queries[i]` you start in the **top left** cell of the matrix and repeat the following process:

* If `queries[i]` is **strictly** greater than the value of the current cell that you are in, then you get one point if it is your first time visiting this cell, and you can move to any **adjacent** cell in all `4` directions: up, down, left, and right.
* Otherwise, you do not get any points, and you end this process.

After the process, `answer[i]` is the **maximum** number of points you can get. **Note** that for each query you are allowed to visit the same cell **multiple** times.

Return _the resulting array_ `answer`.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-number-of-points-from-grid-queries/image0.png) 

**Input:** grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
**Output:** [5,8,1]
**Explanation:** The diagrams above show which cells we visit to get points for each query.

**Example 2:**

![](https://assets.glich.co/dsa/maximum-number-of-points-from-grid-queries/image1.png) 

**Input:** grid = [[5,2,1],[1,1,2]], queries = [3]
**Output:** [0]
**Explanation:** We can not get any points because the value of the top left cell is already greater than or equal to 3.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `2 <= m, n <= 1000`
* `4 <= m * n <= 105`
* `k == queries.length`
* `1 <= k <= 104`
* `1 <= grid[i][j], queries[i] <= 106`

# Approaches
## Brute-Force BFS for Each Query
A straightforward approach is to simulate the process for each query independently. For every query value, we can perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from the top-left cell `(0, 0)` to find all reachable cells.
**Time:** O(k * m * n). For each of the `k` queries, we might perform a BFS that visits all `m * n` cells in the worst case. · **Space:** O(m * n). For each query, we need a `visited` array and a queue, both of which can take up to O(m * n) space in the worst case.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to redundant computations.; Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
### Explanation
This method iterates through each query in the `queries` array one by one. For a given query `q`, it initializes a `visited` grid and a queue to perform a BFS. The search starts from `(0, 0)` only if its value is less than `q`. The BFS then explores all cells `(r, c)` that are reachable from the start through a path of cells where every cell's value is strictly less than `q`. A counter is maintained to track the number of unique cells visited during this traversal. This entire process is repeated for all `k` queries. The main drawback is the massive amount of redundant computation. The set of reachable cells for a smaller query value is always a subset of reachable cells for a larger query value, but this approach re-calculates everything from scratch each time.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[] maxPoints(int[][] grid, int[] queries) {
        int m = grid.length;
        int n = grid[0].length;
        int k = queries.length;
        int[] answer = new int[k];
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        for (int i = 0; i < k; i++) {
            int q = queries[i];
            if (grid[0][0] >= q) {
                answer[i] = 0;
                continue;
            }

            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{0, 0});
            boolean[][] visited = new boolean[m][n];
            visited[0][0] = true;
            int count = 0;

            while (!queue.isEmpty()) {
                int[] curr = queue.poll();
                count++;
                int r = curr[0];
                int c = curr[1];

                for (int j = 0; j < 4; j++) {
                    int nr = r + dr[j];
                    int nc = c + dc[j];

                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] < q) {
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
            answer[i] = count;
        }
        return answer;
    }
}
```
### Algorithm
- For each query `q` with index `i` in `queries`:
    - Initialize `count = 0`.
    - Initialize a queue for Breadth-First Search (BFS) and add the starting cell `(0, 0)`.
    - Initialize a `visited` 2D boolean array to keep track of visited cells for the current query.
    - Check the starting condition: if `grid[0][0] >= q`, the number of points is 0. Set `answer[i] = 0` and proceed to the next query.
    - If `grid[0][0] < q`, mark `(0,0)` as visited and add it to the queue.
    - Start the BFS traversal:
        - While the queue is not empty:
            - Dequeue a cell `(r, c)`.
            - Increment the `count` of reachable cells.
            - For each of its 4 adjacent neighbors `(nr, nc)`:
                - If the neighbor is within the grid boundaries, has not been visited, and its value `grid[nr][nc]` is strictly less than `q`:
                    - Mark the neighbor as visited.
                    - Enqueue the neighbor `(nr, nc)`.
    - After the BFS completes, `count` holds the maximum number of points. Set `answer[i] = count`.

## Offline Processing with Min-Heap
This approach improves upon the brute-force method by avoiding re-computation. It processes queries 'offline', meaning we sort them first. The key observation is that the number of reachable cells is monotonic with the query value. We can process queries in increasing order of their value and incrementally build the connected component of reachable cells using a min-heap.
**Time:** O(k log k + m * n * log(m*n)). We spend O(k log k) for sorting queries. Each of the `m*n` cells is added to and removed from the priority queue at most once, and each heap operation takes O(log(m*n)) time. · **Space:** O(m * n + k). We need O(k) space for storing sorted queries, O(m*n) for the `visited` grid, and O(m*n) for the priority queue in the worst case.
**Pros:** Much more efficient than the brute-force approach.; Correctly leverages the monotonic property of the problem to avoid redundant work.
**Cons:** The `log(m*n)` factor from heap operations can be slightly slower than a Union-Find based approach in practice, although they have the same asymptotic complexity.
### Explanation
Instead of re-calculating for each query, we can process them in a more intelligent order. First, we pair each query with its original index to reconstruct the final answer array later. Then, we sort these pairs based on the query value. This allows us to process smaller queries before larger ones.

We use a min-priority queue (min-heap) to explore the grid, always expanding from the cell with the smallest value on the frontier of our connected component. This is similar to Dijkstra's algorithm for finding shortest paths or Prim's algorithm for minimum spanning trees.

We initialize the heap with the starting cell `(0, 0)`. Then, we iterate through the sorted queries. For each query `q`, we expand our component by repeatedly extracting the minimum-value cell from the heap, as long as its value is less than `q`. When we extract a cell, we increment our `count` of reachable cells and add its unvisited neighbors to the heap. After expanding the component for the current query `q`, the `count` is the answer for this query. We store it in the result array at the query's original index. This way, each grid cell is processed (pushed and popped from the heap) at most once across all queries.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int[] maxPoints(int[][] grid, int[] queries) {
        int m = grid.length;
        int n = grid[0].length;
        int k = queries.length;

        int[][] sortedQueries = new int[k][2];
        for (int i = 0; i < k; i++) {
            sortedQueries[i][0] = queries[i];
            sortedQueries[i][1] = i;
        }
        Arrays.sort(sortedQueries, (a, b) -> a[0] - b[0]);

        int[] answer = new int[k];
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        int count = 0;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        pq.offer(new int[]{grid[0][0], 0, 0});
        visited[0][0] = true;

        for (int i = 0; i < k; i++) {
            int q = sortedQueries[i][0];
            int originalIndex = sortedQueries[i][1];

            while (!pq.isEmpty() && pq.peek()[0] < q) {
                int[] curr = pq.poll();
                count++;
                int r = curr[1];
                int c = curr[2];

                for (int j = 0; j < 4; j++) {
                    int nr = r + dr[j];
                    int nc = c + dc[j];

                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                        visited[nr][nc] = true;
                        pq.offer(new int[]{grid[nr][nc], nr, nc});
                    }
                }
            }
            answer[originalIndex] = count;
        }
        return answer;
    }
}
```
### Algorithm
- Create pairs of `(query, original_index)` to be able to restore the original order of answers. Sort these pairs based on the `query` value in ascending order.
- Initialize a min-priority queue (min-heap) to store tuples of `(value, row, col)`. Add the starting cell `(grid[0][0], 0, 0)` to the heap.
- Initialize a `visited` grid to prevent cycles and re-processing, a `count` of reachable cells to 0, and an `answer` array.
- Iterate through the sorted queries `(q, index)`:
    - While the heap is not empty and the value of the cell at the top of the heap is strictly less than `q`:
        - Pop the cell `(val, r, c)` from the heap.
        - Increment `count`.
        - For each unvisited neighbor `(nr, nc)` of `(r, c)`:
            - Mark the neighbor as visited.
            - Push `(grid[nr][nc], nr, nc)` to the heap.
    - After the inner while loop, `count` represents the total number of cells reachable with a value less than `q`. Store this `count` in `answer[index]`.
- Return the `answer` array.

## Offline Processing with Union-Find
This is the most efficient approach, which also processes queries offline. It models the problem as a dynamic connectivity problem. We process both cells and queries in increasing order of their values. A Union-Find (or Disjoint Set Union) data structure is perfectly suited for tracking connected components and their sizes as we 'activate' more and more cells.
**Time:** O(k log k + m * n * log(m*n)). The dominant costs are sorting the `k` queries and sorting the `m*n` grid cells. The main loop iterates through queries and cells once, with nearly constant time Union-Find operations (amortized O(α(m*n)), where α is the very slow-growing inverse Ackermann function). · **Space:** O(m * n + k). We need O(k) for queries, O(m*n) for the sorted cell list, O(m*n) for the Union-Find data structure, and O(m*n) for the `added` grid.
**Pros:** Conceptually clean and highly efficient for connectivity problems.; Often faster in practice than the min-heap approach due to better memory access patterns from sorting versus scattered heap accesses.
**Cons:** Requires implementing a Union-Find data structure, which adds some complexity.; The initial sorting of all cells might seem like a large upfront cost, though it's asymptotically efficient.
### Explanation
The core idea is to process elements (both grid cells and queries) in a unified, sorted order based on their values. We begin by flattening the grid into a list of cells, each represented by `(value, r, c)`, and then sort this list by `value`. Similarly, we sort the queries by their values, while keeping track of their original indices.

We use a Union-Find data structure, initialized with `m*n` disjoint sets, one for each cell. This data structure is augmented to track the size of each set. We then iterate through the sorted queries. For each query `q`, we first process all cells from our sorted list that have a value less than `q`. When processing a cell `(r, c)`, we 'activate' it and then look at its neighbors. If a neighbor has already been activated (which we can check with a boolean grid), we perform a `union` operation on the two cells. This merges their components and correctly updates the total size of the new component.

After processing all cells with values less than `q`, if the starting cell `(0,0)` has been activated (i.e., `grid[0][0] < q`), the answer is simply the size of the component containing `(0,0)`, which our Union-Find structure can provide in nearly constant time. Otherwise, the answer is 0.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class UnionFind {
    private int[] parent;
    private int[] size;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            if (size[rootI] < size[rootJ]) {
                int temp = rootI;
                rootI = rootJ;
                rootJ = temp;
            }
            parent[rootJ] = rootI;
            size[rootI] += size[rootJ];
        }
    }

    public int getSize(int i) {
        return size[find(i)];
    }
}

class Solution {
    public int[] maxPoints(int[][] grid, int[] queries) {
        int m = grid.length;
        int n = grid[0].length;
        int k = queries.length;

        int[][] sortedQueries = new int[k][2];
        for (int i = 0; i < k; i++) {
            sortedQueries[i][0] = queries[i];
            sortedQueries[i][1] = i;
        }
        Arrays.sort(sortedQueries, (a, b) -> a[0] - b[0]);

        List<int[]> cells = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cells.add(new int[]{grid[i][j], i, j});
            }
        }
        cells.sort((a, b) -> a[0] - b[0]);

        int[] answer = new int[k];
        UnionFind uf = new UnionFind(m * n);
        boolean[][] added = new boolean[m][n];
        int cellIdx = 0;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        for (int i = 0; i < k; i++) {
            int q = sortedQueries[i][0];
            int originalIndex = sortedQueries[i][1];

            while (cellIdx < cells.size() && cells.get(cellIdx)[0] < q) {
                int[] cell = cells.get(cellIdx);
                int r = cell[1];
                int c = cell[2];
                added[r][c] = true;
                int id1 = r * n + c;

                for (int j = 0; j < 4; j++) {
                    int nr = r + dr[j];
                    int nc = c + dc[j];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && added[nr][nc]) {
                        int id2 = nr * n + nc;
                        uf.union(id1, id2);
                    }
                }
                cellIdx++;
            }

            if (added[0][0]) {
                answer[originalIndex] = uf.getSize(0);
            } else {
                answer[originalIndex] = 0;
            }
        }
        return answer;
    }
}
```
### Algorithm
- Create a list of all cells `(value, r, c)` and sort this list by `value`.
- Create pairs `(query, original_index)` and sort them by `query`.
- Initialize a Union-Find (Disjoint Set Union) data structure for `m*n` cells. This structure should also track the size of each disjoint set.
- Initialize a pointer `cell_ptr = 0` for the sorted cell list and a boolean grid `added` to track processed cells.
- Iterate through the sorted queries `(q, index)`:
    - While `cell_ptr` is within bounds and the current cell's value `cells.get(cell_ptr)[0]` is less than `q`:
        - Get the cell `(val, r, c)`.
        - Mark this cell as `added`.
        - For each neighbor `(nr, nc)` that has already been `added`:
            - Union the sets for `(r, c)` and `(nr, nc)`.
        - Increment `cell_ptr`.
    - After the inner loop, check if the starting cell `(0,0)` has been added. If `added[0][0]` is true, the answer is the size of the set containing `(0,0)`, which can be retrieved from the Union-Find structure. Otherwise, the answer is 0.
    - Store the answer at `answer[index]`.
- Return the `answer` array.

# Solutions
### Java

```java
class Solution {
public
  int[] maxPoints(int[][] grid, int[] queries) {
    int k = queries.length;
    int[][] qs = new int[k][2];
    for (int i = 0; i < k; ++i) {
      qs[i] = new int[]{queries[i], i};
    }
    Arrays.sort(qs, (a, b)->a[0] - b[0]);
    int[] ans = new int[k];
    int m = grid.length, n = grid[0].length;
    boolean[][] vis = new boolean[m][n];
    vis[0][0] = true;
    PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0] - b[0]);
    q.offer(new int[]{grid[0][0], 0, 0});
    int[] dirs = new int[]{-1, 0, 1, 0, -1};
    int cnt = 0;
    for (var e : qs) {
      int v = e[0];
      k = e[1];
      while (!q.isEmpty() && q.peek()[0] < v) {
        var p = q.poll();
        ++cnt;
        for (int h = 0; h < 4; ++h) {
          int x = p[1] + dirs[h], y = p[2] + dirs[h + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
            vis[x][y] = true;
            q.offer(new int[]{grid[x][y], x, y});
          }
        }
      }
      ans[k] = cnt;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int dirs[5] = {-1, 0, 1, 0, -1};
  vector<int> maxPoints(vector<vector<int>> &grid, vector<int> &queries) {
    int k = queries.size();
    vector<pair<int, int>> qs(k);
    for (int i = 0; i < k; ++i)
      qs[i] = {queries[i], i};
    sort(qs.begin(), qs.end());
    vector<int> ans(k);
    int m = grid.size(), n = grid[0].size();
    bool vis[m][n];
    memset(vis, 0, sizeof vis);
    vis[0][0] = true;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                   greater<tuple<int, int, int>>>
        q;
    q.push({grid[0][0], 0, 0});
    int cnt = 0;
    for (auto &e : qs) {
      int v = e.first;
      k = e.second;
      while (!q.empty() && get<0>(q.top()) < v) {
        auto [_, i, j] = q.top();
        q.pop();
        ++cnt;
        for (int h = 0; h < 4; ++h) {
          int x = i + dirs[h], y = j + dirs[h + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
            vis[x][y] = true;
            q.push({grid[x][y], x, y});
          }
        }
      }
      ans[k] = cnt;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]: m, n = len(grid), len(grid[0]) qs = sorted((v, i) for i, v in enumerate(queries)) ans = [0] * len(qs) q = [(grid[0][0], 0, 0)] cnt = 0 vis = [[False] * n for _ in range(m)] vis[0][0] = True for v, k in qs: while q and q[0][0] < v: _, i, j = heappop(q) cnt += 1 for a, b in pairwise((- 1, 0, 1, 0, - 1)): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and not vis[x][y]: heappush(q, (grid[x][y], x, y)) vis[x][y] = True ans[k] = cnt return ans

```