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:
Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.
Example 1:
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:
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.lengthn == grid[r].length1 <= m, n <= 1051 <= m * n <= 2 * 105grid[r][c] is either 0 or 1.1 <= stampHeight, stampWidth <= 105Problem Overview: You are given a binary m x n grid where 0 represents empty land and 1 represents blocked cells. You also have a stamp of fixed height and width. The task is to determine whether every empty cell can be covered by one or more stamps without covering any blocked cell. Stamps cannot rotate and must stay inside the grid.
Approach 1: Backtracking Search (Exponential Time)
This approach tries to place stamps recursively across the grid and checks whether all empty cells become covered. For each valid top‑left position, you attempt to place the stamp if all cells inside the rectangle are 0. The algorithm then marks the covered cells and recursively continues exploring the next placements. Because many placements overlap and branch heavily, the search space grows exponentially with grid size. Time complexity is roughly O((m*n) * branching^depth) in the worst case, and space complexity is O(m*n) for recursion state and coverage tracking. This approach demonstrates the brute‑force idea but quickly becomes impractical for large grids.
Approach 2: Greedy with Prefix Sum Optimization (O(m*n))
The optimal strategy avoids explicit placement simulation. Instead, it checks where stamps could be placed and verifies that every empty cell is covered by at least one valid stamp. First build a 2D prefix sum over the grid to query whether any rectangle contains blocked cells in constant time. For each position that could be the top‑left corner of a stamp, use the prefix sum to verify the rectangle is all zeros. If valid, mark the coverage using a 2D difference array so that large rectangular updates happen in constant time.
After processing all candidate positions, compute a prefix accumulation over the difference array to determine how many stamps cover each cell. Finally iterate through the grid: every 0 cell must have coverage greater than zero. If any empty cell remains uncovered, stamping the grid is impossible. This greedy validation works because stamps can overlap freely, so it is safe to mark every valid placement. Time complexity is O(m*n) and space complexity is O(m*n).
The key tools are fast rectangle queries with prefix sum and efficient range updates using a difference grid. The algorithm scans the matrix a constant number of times and greedily records every feasible stamp placement, which guarantees coverage checking without exploring combinations.
Recommended for interviews: The greedy + prefix sum approach is the expected solution. Interviewers want to see that you convert expensive rectangle checks into constant-time queries and avoid brute-force placement. Explaining the backtracking idea first shows you understand the constraints, while implementing the optimized solution demonstrates mastery of greedy reasoning and grid prefix sums.
The goal is to cover all empty (0) cells with stamps without covering any occupied (1) cells and without stamps going out of the grid bounds. Using a greedy approach, we try to place the stamps efficiently. We start by marking all valid positions where a stamp can be fully placed, then check for each empty cell if it can be stamped by overlapping valid positions.
This Python solution uses prefix sum arrays to check if stamps can be placed without covering any occupied cells. It iterates over possible top-left positions of the stamp and ensures it covers only empty cells when placed, modifying the grid to simulate stamping.
Time Complexity: O(m * n), as it performs constant time operations on each cell.
Space Complexity: O(m * n) for the prefix sum array.
This approach attempts to place stamps starting from the top left corner, using a recursive backtracking method. If a position can have a stamp placed while satisfying all conditions (not covering any '1's, staying within bounds, etc.), it proceeds recursively to try further placements. If it hits a dead end, it backtracks to try alternative positions.
This JavaScript solution uses backtracking to attempt placing stamps recursively. If an empty cell is encountered, it checks if a stamp can fit without extending out of boundary or covering any occupied (1) cells. Backtracking allows exploration of different paths to try and cover all empty regions.
JavaScript
Time Complexity: Exponential in the worst case due to the recursive nature of trying all stamp placements.
Space Complexity: O(1) additional space, though recursion adds to call stack usage.
According to the problem description, every empty cell must be covered by a stamp, and no occupied cell can be covered. Therefore, we can traverse the two-dimensional matrix, and for each cell, if all cells in the area of stampHeight times stampWidth with this cell as the upper left corner are empty (i.e., not occupied), then we can place a stamp at this cell.
To quickly determine whether all cells in an area are empty, we can use a two-dimensional prefix sum. We use s_{i,j} to represent the number of occupied cells in the sub-matrix from (1,1) to (i,j) in the two-dimensional matrix. That is, s_{i, j} = s_{i - 1, j} + s_{i, j - 1} - s_{i - 1, j - 1} + grid_{i-1, j-1}.
Then, with (i, j) as the upper left corner, and the height and width are stampHeight and stampWidth respectively, the lower right coordinate of the sub-matrix is (x, y) = (i + stampHeight - 1, j + stampWidth - 1). We can calculate the number of occupied cells in this sub-matrix through s_{x, y} - s_{x, j - 1} - s_{i - 1, y} + s_{i - 1, j - 1}. If the number of occupied cells in this sub-matrix is 0, then we can place a stamp at (i, j). After placing the stamp, all cells in this stampHeight times stampWidth area will become occupied cells. We can use a two-dimensional difference array d to record this change. That is:
$
\begin{aligned}
d_{i, j} &\leftarrow d_{i, j} + 1 \
d_{i, y + 1} &\leftarrow d_{i, y + 1} - 1 \
d_{x + 1, j} &\leftarrow d_{x + 1, j} - 1 \
d_{x + 1, y + 1} &\leftarrow d_{x + 1, y + 1} + 1
\end{aligned}
Finally, we perform a prefix sum operation on the two-dimensional difference array d to find out the number of times each cell is covered by a stamp. If a cell is not occupied and the number of times it is covered by a stamp is 0, then we cannot place a stamp at this cell, so we need to return \texttt{false}. If all "unoccupied cells" are successfully covered by stamps, return \texttt{true}.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n$ are the height and width of the two-dimensional matrix, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Kotlin
| Approach | Complexity |
|---|---|
| Greedy Approach with Prefix Sum Optimization | Time Complexity: O(m * n), as it performs constant time operations on each cell. |
| Backtracking Approach | Time Complexity: Exponential in the worst case due to the recursive nature of trying all stamp placements. |
| Two-Dimensional Prefix Sum + Two-Dimensional Difference | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Placement | Exponential | O(m*n) | Conceptual brute force to understand placement constraints or for very small grids |
| Greedy with Prefix Sum + Difference Grid | O(m*n) | O(m*n) | Optimal solution for large grids; quickly checks valid stamp rectangles and verifies coverage |
Stamping The Grid | Maths | Matrix | Dp | 2132 LeetCode | Leetcode BiWeekly Contest 69 • CodeWithSunny • 2,098 views views
Watch 9 more video solutions →Practice Stamping the Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor