Skip to content

2503. Maximum Number of Points From Grid Queries 👍

  • Time: $O(mn\log mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct T {
  int i;
  int j;
  int val;  // grid[i][j]
  T(int i, int j, int val) : i(i), j(j), val(val) {}
};

class Solution {
 public:
  vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
    const int m = grid.size();
    const int n = grid[0].size();
    const vector<int> dirs{0, 1, 0, -1, 0};
    vector<int> ans(queries.size());
    vector<pair<int, int>> queryAndIndexes;
    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));

    for (int i = 0; i < queries.size(); ++i)
      queryAndIndexes.emplace_back(queries[i], i);

    sort(queryAndIndexes.begin(), queryAndIndexes.end());

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

    for (const auto& [query, index] : queryAndIndexes) {
      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 (int k = 0; k < 4; ++k) {
          const int x = i + dirs[k];
          const int y = j + dirs[k + 1];
          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[index] = accumulate;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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 m = grid.length;
    final int n = grid[0].length;
    final int[] dirs = {0, 1, 0, -1, 0};
    int[] ans = new int[queries.length];
    Pair<Integer, Integer>[] queryAndIndexes = new Pair[queries.length];
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
    boolean[][] seen = new boolean[m][n];

    for (int i = 0; i < queries.length; ++i)
      queryAndIndexes[i] = new Pair<>(queries[i], i);

    Arrays.sort(queryAndIndexes, (a, b) -> a.getKey() - b.getKey());

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

    for (Pair<Integer, Integer> pair : queryAndIndexes) {
      final int query = pair.getKey();
      final int index = pair.getValue();
      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 k = 0; k < 4; ++k) {
          final int x = i + dirs[k];
          final int y = j + dirs[k + 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[index] = accumulate;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
  def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
    m = len(grid)
    n = len(grid[0])
    dirs = [0, 1, 0, -1, 0]
    ans = [0] * len(queries)
    queryAndIndexes = sorted([(query, i) for i, query in enumerate(queries)])
    minHeap = [(grid[0][0], 0, 0)]  # (grid[i][j], i, j)
    seen = {(0, 0)}
    accumulate = 0

    for query, index in queryAndIndexes:
      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 k in range(4):
          x = i + dirs[k]
          y = j + dirs[k + 1]
          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[index] = accumulate

    return ans