2588. Maximum Number Of Points From Grid Queries¶

Difficulty: Hard

2588. Maximum Number of Points From Grid Queries

Hard

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 <= 10⁵
k == queries.length
1 <= k <= 10⁴
1 <= grid[i][j], queries[i] <= 10⁶

Solution¶

class Solution {
    static class Pair {
        int val, ind;
        public Pair(int val, int ind) {
            this.val = val;
            this.ind = ind;
        }
        @Override
        public String toString() {
            return "(" + val + " " + ind + ")";
        }
    }
    static class Tuple {
        int row, col, val;
        public Tuple(int row, int col, int val) {
            this.row = row;
            this.col = col;
            this.val = val;
        }
        @Override
        public String toString() {
            return "(" + row + " " + col + " " + val + ")";
        }
    }
    static class custom_sort implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            return Integer.compare(first.val, second.val);
        }
    }
    static class custom_sort1 implements Comparator<Tuple> {
        @Override
        public int compare(Tuple first, Tuple second) {
            return Integer.compare(first.val, second.val);
        }
    }
    public int[] maxPoints(int[][] grid, int[] queries) {
        int n = grid.length, m = grid[0].length;
        ArrayList<Pair> sorted_queries = new ArrayList<>();
        for (int i = 0; i < queries.length; i++) sorted_queries.add(new Pair(queries[i], i));
        Collections.sort(sorted_queries, new custom_sort());
        int res[] = new int[queries.length];
        PriorityQueue<Tuple> pq = new PriorityQueue<>(new custom_sort1());
        int vis[][] = new int[n + 1][m + 1];
        vis[0][0] = 1;
        int dir[][] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        pq.offer(new Tuple(0, 0, grid[0][0]));
        int count = 0, current_ind = 0;
        while (current_ind < queries.length) {
            while (pq.size() > 0 && pq.peek().val < sorted_queries.get(current_ind).val) {
                count++;
                int cr = pq.peek().row;
                int cc = pq.peek().col;
                int cval = pq.peek().val;
                pq.poll();
                for (int dire[] : dir) {
                    int nr = cr + dire[0];
                    int nc = cc + dire[1];
                    if (nr < n && nr >= 0 && nc < m && nc >= 0 && vis[nr][nc] == 0) {
                        vis[nr][nc] = 1;
                        pq.offer(new Tuple(nr, nc, grid[nr][nc]));
                    }
                }
            }
            res[sorted_queries.get(current_ind).ind] = count;
            current_ind++;
        }
        return res;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here