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

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

<ol>
	<li>Cover all the <strong>empty</strong> cells.</li>
	<li>Do not cover any of the <strong>occupied</strong> cells.</li>
	<li>We can put as <strong>many</strong> stamps as we want.</li>
	<li>Stamps can <strong>overlap</strong> with each other.</li>
	<li>Stamps are not allowed to be <strong>rotated</strong>.</li>
	<li>Stamps must stay completely <strong>inside</strong> the grid.</li>
</ol>

<p>Return <code>true</code> <em>if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return</em> <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex1.png" style="width: 180px; height: 237px;" />
<pre>
<strong>Input:</strong> 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
<strong>Output:</strong> true
<strong>Explanation:</strong> We have two overlapping stamps (labeled 1 and 2 in the image) that are able to cover all the empty cells.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex2.png" style="width: 170px; height: 179px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
<strong>Output:</strong> false 
<strong>Explanation:</strong> There is no way to fit the stamps onto all the empty cells without the stamps going outside the grid.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[r].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>grid[r][c]</code> is either <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= stampHeight, stampWidth &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        # Culprit: The hint is WRONG, please DO NOT use the HINT!!!
        # We can build a 2-d prefix sum array for this. First, for each grid, we try to find if we can put a stamp on its left-top corner. If so, we can mark the grids as covered. Then, we traverse the grids to see if any non-occupied grids can been covered for positive times.
        # A stamp can be large, and we cannot do brute force for the complexity concern. We can leverage 2-d prefix sum array for O(1) of marking a stamp location. Basically, ps(i, j) is the prefix sum of rectangle from (0,0) to (i,j). If we want to increment (i,j) to (i',j') where i < i' and j < j', then we can add ps(i,j) for 1, add ps(i' + 1,j' + 1) for 1 and decrement ps(i, j' + 1) and ps(i' + 1, j).
        m = len(grid)
        n = len(grid[0])
        ps1 = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                ps1[i + 1][j + 1] = ps1[i][j + 1] + ps1[i + 1][j] - ps1[i][j] + grid[i][j]
        ps2 = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m - stampHeight + 1):
            for j in range(n - stampWidth + 1):
                s = ps1[i + stampHeight][j + stampWidth] - ps1[i][j + stampWidth] - ps1[i + stampHeight][j] + ps1[i][j]
                if s == 0:
                    ps2[i][j] += 1
                    ps2[i + stampHeight][j] -= 1
                    ps2[i][j + stampWidth] -= 1
                    ps2[i + stampHeight][j + stampWidth] += 1
        
        cv = [[0] * (n + 1) for _ in range(m + 1)]
        # cv[i][j] == cover number of (i - 1, j - 1).
        for i in range(m):
            for j in range(n):
                cv[i + 1][j + 1] = cv[i][j + 1] + cv[i + 1][j] - cv[i][j] + ps2[i][j]
        for i in range(m):
            for j in range(n):
                if cv[i + 1][j + 1] == 0 and grid[i][j] == 0:
                    return False
        return True
66700