Maximum Number of Points From Grid Queries

Leetcode Problem:

• Maximum Number of Points From Grid Queries

Summary

• Finding Maximum Points in a Grid Based on Queries

Approach

• This solution uses a priority queue to keep track of the cells in the grid that need to be visited
• The priority queue is implemented using a binary heap
• The solution starts from the top left cell and keeps track of the maximum points that can be obtained for each query
• The time complexity is O(m*n*log(m*n)), where m and n are the dimensions of the grid.

Complexity

• O(m*n*log(m*n))

Explanation

• The solution first initializes a visited matrix to keep track of the cells that have been visited
• It also initializes a priority queue with the top left cell of the grid
• Then, it enters a loop where it pops the cell with the maximum value from the priority queue and marks it as visited
• For each cell, it checks all its adjacent cells and pushes them into the priority queue if they have not been visited before
• Finally, it calculates the maximum points that can be obtained for each query by summing up the points obtained for each cell in the priority queue.

Solution Code:

struct _node{
    int r;
    int c;
    int v;
};

template 
struct _heap{
    T arr[1000001];
    int size;
    _heap(){
        size = 1;
    }
    void push(T a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx/2].v > arr[idx].v){
            T t = arr[idx/2];
            arr[idx/2] = arr[idx];
            arr[idx] = t;
            idx /= 2;
        }
    }
    T pop(){
        T ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j >= size) break;
            if(j + 1 < size && arr[j].v > arr[j+1].v){
                j++;
            }
            if(arr[i].v > arr[j].v){
                T t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};

class Solution {
public:
    _heap<_node> h;
    bool visited[1001][1001];
    int answer[1000001] = {0};
    vector maxPoints(vector>& grid, vector& queries) {
        vector ans;
        int cur_query = 0;
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};

        visited[0][0] = true;
        h.push({0, 0, grid[0][0]});
        
        while(!h.empty()){
            _node nod = h.pop();
            cur_query = max(cur_query, nod.v);
            answer[cur_query]++;
            for(int i = 0 ; i < 4; i++){
                int nr = nod.r + dy[i];
                int nc = nod.c + dx[i];
                if(nr < 0 || nr >= grid.size() || nc < 0 || nc >= grid[0].size() || visited[nr][nc]){
                    continue;
                }
                visited[nr][nc] = true;
                h.push({nr, nc, grid[nr][nc]});
            }
        }
        for(int i = 1 ; i < 1000001; i++){
            answer[i] = answer[i-1] + answer[i];
        }
        for(int i = 0 ; i < queries.size(); i++){
            ans.push_back(answer[queries[i]-1]);
        }
        return ans;
    }
};