2132. Stamping the Grid

You are given an m x n binary matrix grid where each cell is either 0 (empty) or 1 (occupied).

You are then given stamps of size stampHeight x stampWidth. We want to fit the stamps such that they follow the given restrictions and requirements:

1. Cover all the empty cells.
2. Do not cover any of the occupied cells.
3. We can put as many stamps as we want.
4. Stamps can overlap with each other.
5. Stamps are not allowed to be rotated.
6. Stamps must stay completely inside the grid.

Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.

c++

class Solution {
    bool judge(vector<vector<int>>& grid) {
        int sum = 0;
        for(auto& r : grid)
            sum += accumulate(begin(r),end(r),0);
        return sum == grid.size() * grid[0].size();
    }
public:
    bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
        int n = grid.size(), m = grid[0].size();
        if(h > n or w > m) return judge(grid);
        vector<int> st(m, 0);
        vector<vector<bool>> mark(n, vector<bool>(m));
        
        for(int i = 0; i < h - 1; i++) { //pre calculate with dp technique
            for(int j = 0; j < m; j++) {
                if(!grid[i][j]) st[j] += 1;
                else st[j] = 0;
            }
        }
        
        for(int i = h - 1; i < n; i++) {
            for(int j = 0; j < m; j++) {// dp technique
                if(!grid[i][j]) st[j] += 1;
                else st[j] = 0;
            }
            queue<int> q;
            for(int j = 0; j < w - 1; j++) { //sliding window technique
                if(st[j] < h) q.push(j);
            }
            for(int l = 0, r = w - 1; r < m; l++,r++) { //marking top left of stamp
                while(!q.empty() and q.front() < l) q.pop();
                if(st[r] < h) q.push(r);
                if(q.empty()) mark[i-h+1][l] = true;
            }
        }
        
        vector<int> row(m + 1);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) { //diff array technique
                if(mark[i][j]) {
                    row[j]++;
                    row[j + w]--;
                }
                if(i >= h and mark[i-h][j]) {
                    row[j]--;
                    row[j + w]++;
                }
            }
            int sum = 0;
            for(int j = 0; j < m; j++) { //prefix sum technique
                sum += row[j];
                if(!sum and !grid[i][j]) {
                    return false;
                }
            }
        }
        
        return true;
    }
};