Stamping the Grid — LeetCode 2132 Python Solution
HardGreedyArrayMatrixPrefix Sum
- Problem
- #2132
- Pattern
- Prefix Sum
- Reading time
- 4 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
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 TrueComplexity
| Measure | Complexity |
|---|---|
| Time | O(m \times n) |
| Space | O(m \times n) auxiliary |
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2132. Stamping the Grid is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
LeetCode 807Max Increase to Keep City SkylineMediumLeetCode 861Score After Flipping MatrixMediumLeetCode 1253Reconstruct a 2-Row Binary MatrixMediumLeetCode 1536Minimum Swaps to Arrange a Binary GridMediumLeetCode 1589Maximum Sum Obtained of Any PermutationMediumLeetCode 1605Find Valid Matrix Given Row and Column SumsMedium
Frequently asked questions
- How hard is LeetCode 2132. Stamping the Grid?
- LeetCode 2132. Stamping the Grid is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2132. Stamping the Grid?
- The Python solution on this page runs in O(m \times n).
- What is the space complexity of LeetCode 2132. Stamping the Grid?
- The Python solution on this page uses O(m \times n) auxiliary space.
- What topics does LeetCode 2132. Stamping the Grid cover?
- LeetCode 2132. Stamping the Grid is tagged Greedy, Array, Matrix and Prefix Sum on LeetCode.