# Stamping the Grid
**Difficulty:** HARD
[External](https://leetcode.com/problems/stamping-the-grid)
Canonical: https://scaleengineer.com/dsa/problems/stamping-the-grid
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## 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**:

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

![](https://assets.glich.co/dsa/stamping-the-grid/image0.png) 

**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:**

![](https://assets.glich.co/dsa/stamping-the-grid/image1.png) 

**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`

# Approaches
## Brute-Force Check per Cell
A straightforward but inefficient approach that directly simulates the process. It first identifies all valid stamp locations by exhaustively checking each potential `stampHeight x stampWidth` rectangle for occupied cells. Then, for each empty cell in the grid, it exhaustively checks if any of the valid stamp placements cover it. This method relies on nested loops and avoids complex data structures.
**Time:** `O(m * n * stampHeight * stampWidth)`. Both finding valid placements and checking coverage involve nested loops that depend on the stamp size, leading to this high complexity. · **Space:** `O(m * n)` to store the `canStamp` grid which indicates possible stamp locations.
**Pros:** The logic is direct and easy to follow, closely mirroring the problem's definition.; Requires minimal complex data structures, mainly just a boolean grid.
**Cons:** The time complexity is very high, making it impractical for the given constraints.; Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms.
### Explanation
This approach tackles the problem with nested loops, making it easy to understand but computationally expensive.

### Algorithm
1.  **Identify All Possible Stamp Placements (Slow Method):**
    *   Create a boolean grid, `canStamp`, of size `m x n`, to store whether a stamp's top-left corner can be placed at `(r, c)`.
    *   Iterate through every possible top-left corner `(r, c)` from `(0, 0)` to `(m - stampHeight, n - stampWidth)`.
    *   For each `(r, c)`, perform a nested loop to scan the entire `stampHeight x stampWidth` area starting from `(r, c)`.
    *   If any cell `(i, j)` within this area has `grid[i][j] == 1`, then this placement is invalid.
    *   If the scan completes without finding any `1`s, mark `canStamp[r][c] = true`.
2.  **Verify Coverage for Each Empty Cell (Slow Method):**
    *   Iterate through every cell `(i, j)` of the original `grid`.
    *   If `grid[i][j] == 0`, we must check if it can be covered.
    *   Initialize a boolean flag `isCovered = false`.
    *   Iterate through all possible top-left corners `(r', c')` that could cover `(i, j)`.
    *   For each such `(r', c')`, check if `canStamp[r'][c']` is `true`. If so, set `isCovered = true` and break.
    *   If after checking all possibilities, `isCovered` is still `false`, return `false`.
3.  **Final Result:**
    *   If the main loop completes, return `true`.

### Code Snippet
```java
class Solution {
    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int m = grid.length;
        int n = grid[0].length;

        // Step 1: Identify all possible stamp placements (slowly)
        boolean[][] canStamp = new boolean[m][n];
        for (int r = 0; r <= m - stampHeight; r++) {
            for (int c = 0; c <= n - stampWidth; c++) {
                boolean possible = true;
                for (int i = 0; i < stampHeight; i++) {
                    for (int j = 0; j < stampWidth; j++) {
                        if (grid[r + i][c + j] == 1) {
                            possible = false;
                            break;
                        }
                    }
                    if (!possible) break;
                }
                if (possible) {
                    canStamp[r][c] = true;
                }
            }
        }

        // Step 2: Verify coverage for each empty cell (slowly)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    boolean isCovered = false;
                    // Check all stamps that could potentially cover (i, j)
                    for (int r = Math.max(0, i - stampHeight + 1); r <= i; r++) {
                        for (int c = Math.max(0, j - stampWidth + 1); c <= j; c++) {
                            // Check if this potential stamp is within bounds and is valid
                            if (r <= m - stampHeight && c <= n - stampWidth && canStamp[r][c]) {
                                isCovered = true;
                                break;
                            }
                        }
                        if (isCovered) break;
                    }
                    if (!isCovered) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}
```
### Algorithm
- Create a boolean grid, `canStamp`, of size `m x n`.
- Iterate through all possible top-left corners `(r, c)` for a stamp.
- For each `(r, c)`, scan the `stampHeight x stampWidth` area. If it contains no `1`s, set `canStamp[r][c] = true`.
- Iterate through every cell `(i, j)` of the original `grid`.
- If `grid[i][j]` is `0`, check if there exists a valid stamp placement `(r', c')` (where `canStamp[r'][c']` is true) that covers `(i, j)`.
- If any empty cell `(i, j)` cannot be covered, return `false`.
- If all empty cells are coverable, return `true`.

## 2D Prefix Sum and Difference Array
This optimal approach reframes the problem to efficiently handle rectangular queries and updates. It first uses a 2D prefix sum array to quickly find all valid stamp placements in `O(m*n)` time. Then, instead of checking coverage for each cell individually, it uses a 2D difference array (a sweep-line technique) to mark all covered regions simultaneously. By calculating a prefix sum on this difference array, we can determine which empty cells are covered, leading to an overall optimal solution.
**Time:** `O(m * n)`. Each of the major steps—calculating prefix sums, finding possible stamps, applying the difference array, and final verification—takes linear time with respect to the number of cells in the grid. · **Space:** `O(m * n)`. Several auxiliary grids (`prefixOnes`, `possibleStamps`, `covered`) are needed, each with a size proportional to the input grid.
**Pros:** Optimal time complexity, making it efficient enough for large grids.; Demonstrates a powerful and reusable pattern (prefix sums/difference arrays) for grid problems.
**Cons:** Requires more auxiliary space compared to the naive approach.; The logic, especially for the 2D difference array and prefix sums, can be complex to implement correctly.
### Explanation
This approach solves the problem efficiently by leveraging two powerful techniques for grid manipulation: 2D prefix sums and 2D difference arrays. The core idea is to work backward from the requirements.

### Algorithm
1.  **Calculate Prefix Sum of Occupied Cells:**
    *   Create a 2D prefix sum array, `prefixOnes`, of size `(m+1) x (n+1)`. `prefixOnes[i+1][j+1]` will store the total count of `1`s in the rectangle from `(0, 0)` to `(i, j)`. This allows `O(1)` lookup for the number of `1`s in any sub-rectangle.
2.  **Identify All Possible Stamp Placements:**
    *   Create a grid, `possibleStamps`, of size `m x n`.
    *   Iterate through every possible top-left corner `(r, c)`. Use the `prefixOnes` array to check if the `stampHeight x stampWidth` rectangle contains any `1`s.
    *   If the rectangle is empty of `1`s, mark it as a possible placement.
3.  **Calculate Coverage using a 2D Difference Array:**
    *   To find the union of all possible stamp areas efficiently, we use a 2D difference array `diff`.
    *   For each possible stamp placement at `(r, c)`, we update four points in `diff` to represent the addition of this rectangular area.
4.  **Reconstruct the Coverage Grid:**
    *   By calculating the 2D prefix sum of the `diff` array, we obtain a `covered` grid where `covered[i][j]` equals the total number of valid stamps covering cell `(i, j)`.
5.  **Final Verification:**
    *   Iterate through the original `grid`. If any cell `(i, j)` is empty (`grid[i][j] == 0`) but is not covered (`covered[i][j] == 0`), it's impossible to stamp the grid. Return `false`.
    *   If all empty cells are covered, return `true`.

### Code Snippet
```java
class Solution {
    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int m = grid.length;
        int n = grid[0].length;

        // 1. Calculate prefix sum of occupied cells (1s)
        int[][] prefixOnes = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixOnes[i + 1][j + 1] = grid[i][j] + prefixOnes[i][j + 1] + prefixOnes[i + 1][j] - prefixOnes[i][j];
            }
        }

        // 2. Identify all possible stamp placements
        int[][] possibleStamps = new int[m][n];
        for (int r = 0; r <= m - stampHeight; r++) {
            for (int c = 0; c <= n - stampWidth; c++) {
                int r1 = r, c1 = c;
                int r2 = r + stampHeight - 1;
                int c2 = c + stampWidth - 1;
                int sum = prefixOnes[r2 + 1][c2 + 1] - prefixOnes[r1][c2 + 1] - prefixOnes[r2 + 1][c1] + prefixOnes[r1][c1];
                if (sum == 0) {
                    possibleStamps[r][c] = 1;
                }
            }
        }

        // 3. & 4. Use difference array to calculate coverage
        int[][] covered = new int[m + 1][n + 1];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (possibleStamps[r][c] == 1) {
                    int r_end = r + stampHeight;
                    int c_end = c + stampWidth;
                    covered[r][c]++;
                    if (r_end < m + 1) covered[r_end][c]--;
                    if (c_end < n + 1) covered[r][c_end]--;
                    if (r_end < m + 1 && c_end < n + 1) covered[r_end][c_end]++;
                }
            }
        }

        // Compute prefix sum on the difference array
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0) covered[i][j] += covered[i - 1][j];
                if (j > 0) covered[i][j] += covered[i][j - 1];
                if (i > 0 && j > 0) covered[i][j] -= covered[i - 1][j - 1];
            }
        }

        // 5. Final verification
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && covered[i][j] == 0) {
                    return false;
                }
            }
        }

        return true;
    }
}
```
### Algorithm
- Create a 2D prefix sum array, `prefixOnes`, to count `1`s in any rectangle in `O(1)`.
- Use `prefixOnes` to identify all valid stamp placements (rectangles with zero `1`s) and store them in a `possibleStamps` grid. This takes `O(m*n)`.
- Create a 2D difference array, `diff`.
- For each valid stamp placement at `(r, c)`, increment/decrement the four corners of the corresponding rectangle in the `diff` array.
- Compute a 2D prefix sum on the `diff` array to get a final `covered` grid. `covered[i][j]` will store the number of stamps covering cell `(i, j)`.
- Iterate through the grid. If `grid[i][j] == 0` and `covered[i][j] == 0`, return `false`.
- If the loop completes, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
    int m = grid.length, n = grid[0].length;
    int[][] s = new int[m + 1][n + 1];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s[i][j] =
            s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1];
      }
    }
    int[][] d = new int[m + 2][n + 2];
    for (int i = 1; i + stampHeight - 1 <= m; ++i) {
      for (int j = 1; j + stampWidth - 1 <= n; ++j) {
        int x = i + stampHeight - 1, y = j + stampWidth - 1;
        if (s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] == 0) {
          d[i][j]++;
          d[i][y + 1]--;
          d[x + 1][j]--;
          d[x + 1][y + 1]++;
        }
      }
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
        if (grid[i - 1][j - 1] == 0 && d[i][j] == 0) {
          return false;
        }
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} grid * @param {number} stampHeight * @param {number} stampWidth * @return {boolean} */ var possibleToStamp =
  function (grid, stampHeight, stampWidth) {
    const m = grid.length;
    const n = grid[0].length;
    const s = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    for (let i = 1; i <= m; ++i) {
      for (let j = 1; j <= n; ++j) {
        s[i][j] =
          s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1];
      }
    }
    const d = Array.from({ length: m + 2 }, () => Array(n + 2).fill(0));
    for (let i = 1; i + stampHeight - 1 <= m; ++i) {
      for (let j = 1; j + stampWidth - 1 <= n; ++j) {
        const [x, y] = [i + stampHeight - 1, j + stampWidth - 1];
        if (s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] === 0) {
          d[i][j]++;
          d[i][y + 1]--;
          d[x + 1][j]--;
          d[x + 1][y + 1]++;
        }
      }
    }
    for (let i = 1; i <= m; ++i) {
      for (let j = 1; j <= n; ++j) {
        d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
        if (grid[i - 1][j - 1] === 0 && d[i][j] === 0) {
          return false;
        }
      }
    }
    return true;
  };

```

### CPP

```cpp
class Solution {
public:
  bool possibleToStamp(vector<vector<int>> &grid, int stampHeight,
                       int stampWidth) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> s(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s[i][j] =
            s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1];
      }
    }
    vector<vector<int>> d(m + 2, vector<int>(n + 2));
    for (int i = 1; i + stampHeight - 1 <= m; ++i) {
      for (int j = 1; j + stampWidth - 1 <= n; ++j) {
        int x = i + stampHeight - 1, y = j + stampWidth - 1;
        if (s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] == 0) {
          d[i][j]++;
          d[i][y + 1]--;
          d[x + 1][j]--;
          d[x + 1][y + 1]++;
        }
      }
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
        if (grid[i - 1][j - 1] == 0 && d[i][j] == 0) {
          return false;
        }
      }
    }
    return true;
  }
};

```

### Python

```python
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, 1): for j, v in enumerate(row, 1): s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v d = [[0] * (n + 2) for _ in range(m + 2)] for i in range(1, m - stampHeight + 2): for j in range(1, n - stampWidth + 2): x, y = i + stampHeight - 1, j + stampWidth - 1 if s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] == 0: d[i][j] += 1 d[i][y + 1] -= 1 d[x + 1][j] -= 1 d[x + 1][y + 1] += 1 for i, row in enumerate(grid, 1): for j, v in enumerate(row, 1): d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] if v == 0 and d[i][j] == 0: return False return True

```