2503. Maximum Number of Points From Grid Queries LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2503. Maximum Number of Points From Grid Queries LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Points From Grid Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Number of Points From Grid Queries solution in C++
Maximum Number of Points From Grid Queries solution in Java
Maximum Number of Points From Grid Queries solution in Python
Additional Resources

2503. Maximum Number of Points From Grid Queries LeetCode Solution image

Problem Statement of Maximum Number of Points From Grid Queries

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:

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:

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

Complexity Analysis

Time Complexity: O(mn\log mn)
Space Complexity: O(mn)

2503. Maximum Number of Points From Grid Queries LeetCode Solution in C++

struct IndexedQuery {
  int queryIndex;
  int query;
};

struct T {
  int i;
  int j;
  int val;  // grid[i][j]
};

class Solution {
 public:
  vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = grid.size();
    const int n = grid[0].size();
    vector<int> ans(queries.size());
    auto compare = [](const T& a, const T& b) { return a.val > b.val; };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
    vector<vector<bool>> seen(m, vector<bool>(n));

    minHeap.emplace(0, 0, grid[0][0]);
    seen[0][0] = true;
    int accumulate = 0;

    for (const auto& [queryIndex, query] : getIndexedQueries(queries)) {
      while (!minHeap.empty()) {
        const auto [i, j, val] = minHeap.top();
        minHeap.pop();
        if (val >= query) {
          // The smallest neighbor is still larger than `query`, so no need to
          // keep exploring. Re-push (i, j, grid[i][j]) back to the `minHeap`.
          minHeap.emplace(i, j, val);
          break;
        }
        ++accumulate;
        for (const auto& [dx, dy] : dirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          if (seen[x][y])
            continue;
          minHeap.emplace(x, y, grid[x][y]);
          seen[x][y] = true;
        }
      }
      ans[queryIndex] = accumulate;
    }

    return ans;
  }

 private:
  vector<IndexedQuery> getIndexedQueries(const vector<int>& queries) {
    vector<IndexedQuery> indexedQueries;
    for (int i = 0; i < queries.size(); ++i)
      indexedQueries.push_back({i, queries[i]});
    ranges::sort(
        indexedQueries, ranges::less{},
        [](const IndexedQuery& indexedQuery) { return indexedQuery.query; });
    return indexedQueries;
  }
};
/* code provided by PROGIEZ */

2503. Maximum Number of Points From Grid Queries LeetCode Solution in Java

class T {
  public int i;
  public int j;
  public int val; // grid[i][j]
  public T(int i, int j, int val) {
    this.i = i;
    this.j = j;
    this.val = val;
  }
}

class Solution {
  public int[] maxPoints(int[][] grid, int[] queries) {
    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = grid.length;
    final int n = grid[0].length;
    int[] ans = new int[queries.length];
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
    boolean[][] seen = new boolean[m][n];

    minHeap.offer(new T(0, 0, grid[0][0]));
    seen[0][0] = true;
    int accumulate = 0;

    for (IndexedQuery indexedQuery : getIndexedQueries(queries)) {
      final int queryIndex = indexedQuery.queryIndex;
      final int query = indexedQuery.query;
      while (!minHeap.isEmpty()) {
        final int i = minHeap.peek().i;
        final int j = minHeap.peek().j;
        final int val = minHeap.poll().val;
        if (val >= query) {
          // The smallest neighbor is still larger than `query`, so no need to
          // keep exploring. Re-push (i, j, grid[i][j]) back to the `minHeap`.
          minHeap.offer(new T(i, j, val));
          break;
        }
        ++accumulate;
        for (int[] dir : dirs) {
          final int x = i + dir[0];
          final int y = j + dir[1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          if (seen[x][y])
            continue;
          minHeap.offer(new T(x, y, grid[x][y]));
          seen[x][y] = true;
        }
      }
      ans[queryIndex] = accumulate;
    }

    return ans;
  }

  private record IndexedQuery(int queryIndex, int query){};

  private IndexedQuery[] getIndexedQueries(int[] queries) {
    IndexedQuery[] indexedQueries = new IndexedQuery[queries.length];
    for (int i = 0; i < queries.length; ++i)
      indexedQueries[i] = new IndexedQuery(i, queries[i]);
    Arrays.sort(indexedQueries, (a, b) -> Integer.compare(a.query, b.query));
    return indexedQueries;
  }
}
// code provided by PROGIEZ

2503. Maximum Number of Points From Grid Queries LeetCode Solution in Python

from dataclasses import dataclass


@dataclass(frozen=True)
class IndexedQuery:
  queryIndex: int
  query: int

  def __iter__(self):
    yield self.queryIndex
    yield self.query


class Solution:
  def maxPoints(self, grid: list[list[int]], queries: list[int]) -> list[int]:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(grid)
    n = len(grid[0])
    ans = [0] * len(queries)
    minHeap = [(grid[0][0], 0, 0)]  # (grid[i][j], i, j)
    seen = {(0, 0)}
    accumulate = 0

    for queryIndex, query in sorted([IndexedQuery(i, query)
                                     for i, query in enumerate(queries)],
                                    key=lambda x: x.query):
      while minHeap:
        val, i, j = heapq.heappop(minHeap)
        if val >= query:
          # The smallest neighbor is still larger than `query`, so no need to
          # keep exploring. Re-push (i, j, grid[i][j]) back to the `minHeap`.
          heapq.heappush(minHeap, (val, i, j))
          break
        accumulate += 1
        for dx, dy in dirs:
          x = i + dx
          y = j + dy
          if x < 0 or x == m or y < 0 or y == n:
            continue
          if (x, y) in seen:
            continue
          heapq.heappush(minHeap, (grid[x][y], x, y))
          seen.add((x, y))
      ans[queryIndex] = accumulate

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents