Maximum number of points from grid queries

Array Two Pointers Breadth-First Search Union-Find Sorting Heap (Priority Queue) Matrix

59.3% acceptance

Feb 25, 2026

1100

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_points(grid: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    let m = grid.len();
    let n = grid[0].len();
    let k = queries.len();

    let mut sorted_q: Vec<(i32, usize)> =
      queries.iter().enumerate().map(|(i, &q)| (q, i)).collect();
    sorted_q.sort_unstable();

    let mut answer = vec![0i32; k];
    let mut heap: BinaryHeap<Reverse<(i32, usize, usize)>> = BinaryHeap::new();
    let mut visited = vec![vec![false; n]; m];
    let mut count = 0i32;

    heap.push(Reverse((grid[0][0], 0, 0)));
    visited[0][0] = true;

    let dirs = [(0i32, 1i32), (0, -1), (1, 0), (-1, 0)];

    for (q, idx) in sorted_q {
      while let Some(&Reverse((val, r, c))) = heap.peek() {
        if val < q {
          heap.pop();
          count += 1;
          for (dr, dc) in &dirs {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 {
              let nr = nr as usize;
              let nc = nc as usize;
              if !visited[nr][nc] {
                visited[nr][nc] = true;
                heap.push(Reverse((grid[nr][nc], nr, nc)));
              }
            }
          }
        } else {
          break;
        }
      }
      answer[idx] = count;
    }
    answer
  }
}