Formatted question description: https://leetcode.ca/all/2132.html

2132. Stamping the Grid

Difficulty: Hard.
Related Topics: Array, Greedy, Matrix, Prefix Sum.
Similar Questions: Maximal Square, Bomb Enemy, Matrix Block Sum.

Problem

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:

Cover all the empty cells.
Do not cover any of the occupied cells.
We can put as many stamps as we want.
Stamps can overlap with each other.
Stamps are not allowed to be rotated.
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.

Example 1:

Input: grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
Output: true
Explanation: We have two overlapping stamps (labeled 1 and 2 in the image) that are able to cover all the empty cells.

Example 2:

Input: grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
Output: false 
Explanation: There is no way to fit the stamps onto all the empty cells without the stamps going outside the grid.

Constraints:

m == grid.length
n == grid[r].length
1 <= m, n <= 105
1 <= m * n <= 2 * 105
grid[r][c] is either 0 or 1.
1 <= stampHeight, stampWidth <= 105

Solution

class Solution {
    private boolean canPaved(int[][] grid, int is, int js, int ie, int je) {
        for (int i = is; i <= ie; i++) {
            for (int j = js; j <= je; j++) {
                if (grid[i][j] == 1) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean possibleToStamp(int[][] grid, int h, int w) {
        int rl = grid[0].length;
        for (int i = 0; i < grid.length; i++) {
            int[] row = grid[i];
            int prev = -1;
            for (int j = 0; j < row.length; j++) {
                if (row[j] == 0) {
                    if (j + 1 < rl
                            && row[j + 1] == 1
                            && j - w + 1 >= 0
                            && i + 1 < grid.length
                            && grid[i + 1][j] == 1
                            && i - h + 1 >= 0
                            && canPaved(grid, i - h + 1, j - w + 1, i, j)) {
                        return false;
                    }
                    continue;
                }
                if (1 < j - prev && j - prev <= w) {
                    return false;
                }
                prev = j;
            }
            if (1 < row.length - prev && row.length - prev <= w) {
                return false;
            }
        }
        for (int i = 0; i < rl; i++) {
            int prev = -1;
            for (int j = 0; j < grid.length; j++) {
                if (grid[j][i] == 0) {
                    continue;
                }
                if (1 < j - prev && j - prev <= h) {
                    return false;
                }
                prev = j;
            }
            if (1 < grid.length - prev && grid.length - prev <= h) {
                return false;
            }
        }
        return true;
    }
}

```
Todo
```

class Solution:
    def possibleToStamp(
        self, grid: List[List[int]], stampHeight: int, stampWidth: int
    ) -> bool:
        m, n = len(grid), len(grid[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + v

        d = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v == 0:
                    x, y = i + stampHeight, j + stampWidth
                    if x <= m and y <= n and s[x][y] - s[x][j] - s[i][y] + s[i][j] == 0:
                        d[i][j] += 1
                        d[i][y] -= 1
                        d[x][j] -= 1
                        d[x][y] += 1

        cnt = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                cnt[i + 1][j + 1] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j]
                if v == 0 and cnt[i + 1][j + 1] == 0:
                    return False
        return True

############

# 2132. Stamping the Grid
# https://leetcode.com/problems/stamping-the-grid/

class Solution:
    def possibleToStamp(self, grid: List[List[int]], H: int, W: int) -> bool:
        rows, cols = len(grid), len(grid[0])
        prefix = [[0] * (cols + 1) for _ in range(rows + 1)]

        for x in range(rows):
            for y in range(cols):
                prefix[x + 1][y + 1] = prefix[x + 1][y] + prefix[x][y + 1] - prefix[x][y] + grid[x][y]

        diff = [[0] * (cols + 1) for _ in range(rows + 1)]
        
        for x in range(rows - H + 1):
            for y in range(cols - W + 1):
                rect = prefix[x + H][y + W] - prefix[x + H][y] - prefix[x][y + W] + prefix[x][y]

                if rect == 0:
                    diff[x][y] += 1
                    diff[x + H][y] -= 1
                    diff[x][y + W] -= 1
                    diff[x + H][y + W] += 1

        for x in range(rows + 1):
            for y in range(cols):
                diff[x][y + 1] += diff[x][y]
        
        for y in range(cols + 1):
            for x in range(rows):
                diff[x + 1][y] += diff[x][y]
        
        for x in range(rows):
            for y in range(cols):
                if grid[x][y] == 0 and diff[x][y] == 0:
                    return False
        
        return True
                    

Explain:

nope.

Complexity:

Time complexity : O(n).
Space complexity : O(n).

2132 - Stamping the Grid

2132. Stamping the Grid

Problem

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

2132. Stamping the Grid

Problem

Solution

All Problems

All Solutions