<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]], h: int, w: int) -> bool:
        R = len(grid)
        C = len(grid[0])

        # we have a single stamp of size h x w

        # must cover all cells
        # cannot cover occupied cells
        # stamps can overlap
        # stamps cannot be rotated
        # stamps must stay inside the grid

        # so we need to stamp over all 0s in the grid, cannot stamp over ones

        if h == w == 1: return True


        # oof need a clever insight for this to avoid O(R*C * h*w) scaling or similar


        # WAIT MAYBE I GOT IT
        #    1. first we can find all upper-left stamp locations: O(R*C) cumulative sum, find upper-lefts with zero sum
        #    2. then if we need to stamp r,c then we must have at least one upper-left stampable location that reaches this
        #       bottom-right position, so find count of stampable upper-left locations at r-h+1:r+1 and c-w+1:c+1

        # we'll do bottom-right because it's more tractable that way

        mustStamp = [(r, c) for r in range(R) for c in range(C) if grid[r][c] == 0]

        if not mustStamp: return True

        if h > R or w > C: return False # fixed: if no stampable locations exist then we should return true even if stamp doesn't fit

        # find all obstacles at in 0..r and 0..c for all r, c
        for c in range(1, C): grid[0][c] += grid[0][c-1]
        for r in range(1, R):
            rsum = 0
            for c in range(C):
                rsum += grid[r][c]
                grid[r][c] = rsum + grid[r-1][c]

        # indicate bottom-right cells of valid stampable regions
        stampable = [[0]*C for _ in range(R)]
        for r in range(h-1, R):
            for c in range(w-1, C):
                obstacles = grid[r][c]
                if c-w+1:
                    obstacles -= grid[r][c-w]
                if r-h+1:
                    obstacles -= grid[r-h][c]
                if c-w+1 and r-h+1:
                    obstacles += grid[r-h][c-w] # if both, we double-subtracted this region so add one multiple back

                if not obstacles: stampable[r][c] = 1

        # in-place transform so stampable[r][c] is number of bottom-right stamp locations in 0..r x 0..c
        for c in range(1, C): stampable[0][c] += stampable[0][c-1]
        for r in range(1, R):
            rsum = 0
            for c in range(C):
                rsum += stampable[r][c]
                stampable[r][c] = rsum + stampable[r-1][c]

        # print(f"grid")
        # for row in grid: print(row)

        # print()
        # print(f"stampable")
        # for row in stampable: print(row)

        # final answer: for each location we must stamp, see how many bottom-right locations
        # we can stamp where that stamp will cover this cell
        for r, c in mustStamp:
            sr = min(R-1, r+h-1)
            sc = min(C-1, c+w-1)
            # any stamp whose bottom-right cell is in r..sr x c..sc will work

            count = stampable[sr][sc]
            if r:
                count -= stampable[r-1][sc]
            if c:
                count -= stampable[sr][c-1]
            if r and c:
                count += stampable[r-1][c-1]

            if count == 0: return False

        return True
60300