1
class Solution:
2
    def prefix_sum(self, grid: List[List[int]]) -> List[List[int]]:
3
        ps = [
4
            [grid[row][col] for col in range(len(grid[0]))] for row in range(len(grid))
5
        ]
6

7
        for row in range(len(grid)):
8
            for col in range(1, len(grid[0])):
9
                ps[row][col] = ps[row][col - 1] + grid[row][col]
10

11
        for row in range(1, len(grid)):
12
            for col in range(len(grid[0])):
13
                ps[row][col] = ps[row - 1][col] + ps[row][col]
14

15
        return ps
16

17
    def sumRegion(self, ps, row1: int, col1: int, row2: int, col2: int) -> int:
18
        ans = 0
19
        if row1 == 0 and col1 == 0:
20
            ans = ps[row2][col2]
21
        elif row1 == 0:
22
            ans = ps[row2][col2] - ps[row2][col1 - 1]
23
        elif col1 == 0:
24
            ans = ps[row2][col2] - ps[row1 - 1][col2]
25
        else:
26
            ans = (
27
                ps[row2][col2]
28
                - ps[row1 - 1][col2]
29
                - ps[row2][col1 - 1]
30
                + ps[row1 - 1][col1 - 1]
31
            )
32
        return ans
33

34
    def possibleToStamp(
35
        self, grid: List[List[int]], stampHeight: int, stampWidth: int
36
    ) -> bool:
37
        diff = [[0 for col in range(len(grid[0]) + 1)] for row in range(len(grid) + 1)]
38

39
        ps = self.prefix_sum(grid)
40
        cover = 0
41

42
        for row in range(len(grid) - (stampHeight - 1)):
43
            for col in range(len(grid[0]) - (stampWidth - 1)):
44
                sub_sum = self.sumRegion(
45
                    ps, row, col, row + stampHeight - 1, col + stampWidth - 1
46
                )
47
                if sub_sum == 0:
48
                    diff[row][col] += 1
49
                    diff[row][col + stampWidth] -= 1
50
                    diff[row + stampHeight][col] -= 1
51
                    diff[row + stampHeight][col + stampWidth] = 1
52
        pref_diff = self.prefix_sum(diff)
53
        m, n = len(grid), len(grid[0])
54

55
        for row in range(len(grid)):
56
            for col in range(len(grid[0])):
57
                if grid[row][col] == 0 and pref_diff[row][col] == 0:
58
                    return False
59

60
        return True