<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:
        # inspired by /range-sum-query-2d-immutable
        # the idea is to pre calculate the prefix sum of 2d and store it in a dp array
        # now, when you check a aprticular regiion for its sum and its >0, that means its an occupied cell
        # and that we cant put a stamp there
        # now that preprocessing is done, we need to place stamps
        # similar to above strat, we precalc the stamp placements area and store it in stamps
        # we check bottom right of a region to mark it(set True) with a stamp, 
        # now when we check the new grid for stamps, we check fi region sum is 0 if region sum is 0, no stamps 
        # were placed

        # func to pre calc the prefix sums of 2d array
        def pref2d(mat, m,n):
            dp = [ [0]*(n+1) for _ in range(m+1)]
            for i in range(m):
                for j in range(n):
                    dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] + mat[i][j] - dp[i][j]
            
            return dp
        
        # func to get sum fo a particular region given cordinates
        def sum_region(mat, r1, c1, r2, c2):
            return mat[r2+1][c2+1] + mat[r1][c1] - mat[r1][c2+1] - mat[r2+1][c1]
        
        m,n = len(grid), len(grid[0])
        # precalc sums
        pref = pref2d(grid, m,n)
        stamp = [[0]*n for _ in range(m)]
        # mark if we can palce stamps in an area
        for i in range(stampHeight-1, m):
            for j in range(stampWidth-1, n):
                # check if region sum is 0, if yes amnrk true,
                # send stamp dimensions to sum func, i, is bottom right of the region
                stamp[i][j] = sum_region(pref, i-stampHeight+1, j-stampWidth+1, i, j ) == 0

        # now pre calc prefix sums after placing stamps to determine if we can fully place stamps
        pref2 = pref2d(stamp,m,n)
        for i in range(m):
            for j in range(n):
                #check if grid and sum == 0 as if both are 0, means we havent placed any stamp
                if grid[i][j] == 0 and sum_region(pref2, i, j, min(m-1, i+stampHeight-1), min(n-1, j+stampWidth-1)) == 0:
                    return False
        
        return True
61300