Stamping the Grid solution and explanation
9 more videos on this problem
Stamping The Grid | Maths | Matrix | Dp | 2132 LeetCode | Leetcode BiWeekly Contest 69CodeWithSunny · 25:05 · 2K views
2132. Stamping the Grid ( Leetcode Problem: Biweekly Contest 69)viralSongs · 11:28 · 1K views
Leetcode Biweekly 69 (Stamping the Grid)Soumya Bhattacharjee · 10:00 · 1K views
2D Prefix Sum Interview Pattern | 2132 Stamping The Grid: Leetcode HardBharat Khanna · 23:21 · 1K views
【每日一题】LeetCode 2132. Stamping the GridHuifeng Guan · 42:45 · 812 views
5931. Stamping the Grid (Leetcode Problem)viralSongs · 2:33 · 761 views
2132. Stamping the Grid (Leetcode Hard)Programming Live with Larry · 1:30:56 · 682 views
2132. Stamping the Grid (Upsolve)Clayton Wong · 27:27 · 82 views
Leetcode 2132. Stamping the Grid (2d difference array)LetsCode · 33:52 · 65 views
Leetcode 2132Retriever · 5:02 · 34 views
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. We want to fit the stamps such that they follow the given restrictions and requirements:
- Cover all the empty cells.
- Do not cover any of the occupied cells.
- We can put as many stamps as we want.
- Stamps can overlap with each other.
- Stamps are not allowed to be rotated.
- 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:
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 either0or1.1 <= stampHeight, stampWidth <= 105
Approach overview
Problem 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.
Approach 1: Greedy Approach with Prefix Sum Optimization
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.
def can_cover(grid, stampHeight, stampWidth):
m, n = len(grid), len(grid[0])
prefix_sum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
prefix_sum[i + 1][j + 1] = grid[i][j] + prefix_sum[i][j + 1] + prefix_sum[i + 1][j] - prefix_sum[i][j]
for i in range(m - stampHeight + 1):
for j in range(n - stampWidth + 1):
total_sum = prefix_sum[i + stampHeight][j + stampWidth] - prefix_sum[i + stampHeight][j] - prefix_sum[i][j + stampWidth] + prefix_sum[i][j]
if total_sum == 0:
for x in range(i, i + stampHeight):
for y in range(j, j + stampWidth):
grid[x][y] = 2
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
return False
return True
# Example usage with test case 1:
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
print(can_cover(grid, stampHeight, stampWidth))#include <vector>
#include <iostream>
using namespace std;
bool canCover(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> prefixSum(m + 1, vector<int>(n + 1, 0));
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
prefixSum[i + 1][j + 1] = grid[i][j] + prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j];
}
}
for(int i = 0; i <= m - stampHeight; ++i) {
for(int j = 0; j <= n - stampWidth; ++j) {
int totalSum = prefixSum[i + stampHeight][j + stampWidth] - prefixSum[i + stampHeight][j] - prefixSum[i][j + stampWidth] + prefixSum[i][j];
if (totalSum == 0) {
for(int x = i; x < i + stampHeight; ++x) {
for(int y = j; y < j + stampWidth; ++y) {
grid[x][y] = 2;
}
}
}
}
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(grid[i][j] == 0)
return false;
}
}
return true;
}
int main() {
vector<vector<int>> grid = {{1,0,0,0},{1,0,0,0},{1,0,0,0},{1,0,0,0},{1,0,0,0}};
int stampHeight = 4;
int stampWidth = 3;
cout << canCover(grid, stampHeight, stampWidth) << endl;
return 0;
}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.
Approach 2: Backtracking Approach
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.
function canCover(grid, stampHeight, stampWidth) {
const m = grid.length;
const n = grid[0].length;
const canStamp = (row, col) => {
for (let i = row; i < row + stampHeight; i++) {
for (let j = col; j < col + stampWidth; j++) {
if (grid[i][j] !== 0) return false;
}
}
return true;
};
const placeStamp = (row, col) => {
for (let i = row; i < row + stampHeight; i++) {
for (let j = col; j < col + stampWidth; j++) {
grid[i][j] = 2;
}
}
};
const backtrack = (row, col) => {
if (row >= m) return true;
if (col >= n) return backtrack(row + 1, 0);
if (grid[row][col] === 0) {
if (row + stampHeight <= m && col + stampWidth <= n && canStamp(row, col)) {
placeStamp(row, col);
if (backtrack(row, col + 1)) return true;
for (let i = row; i < row + stampHeight; i++) {
for (let j = col; j < col + stampWidth; j++) {
grid[i][j] = 0;
}
}
}
return false;
}
return backtrack(row, col + 1);
};
return backtrack(0, 0);
}
const grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]];
const stampHeight = 4;
const stampWidth = 3;
console.log(canCover(grid, stampHeight, stampWidth));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.
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.
Approach 3: Two-Dimensional Prefix Sum + Two-Dimensional Difference
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.
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;
}
}function possibleToStamp(grid: number[][], stampHeight: number, stampWidth: number): boolean {
const m = grid.length;
const n = grid[0].length;
const s: number[][] = 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: number[][] = 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;
}func possibleToStamp(grid [][]int, stampHeight int, stampWidth int) bool {
m, n := len(grid), len(grid[0])
s := make([][]int, m+1)
for i := range s {
s[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for 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]
}
}
d := make([][]int, m+2)
for i := range d {
d[i] = make([]int, n+2)
}
for i := 1; i+stampHeight-1 <= m; i++ {
for j := 1; j+stampWidth-1 <= n; j++ {
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 i := 1; i <= m; i++ {
for 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
}class Solution {
fun possibleToStamp(grid: Array<IntArray>, stampHeight: Int, stampWidth: Int): Boolean {
val m = grid.size
val n = grid[0].size
var prefix_sums_matrix = Array(m + 1) { IntArray(n + 1) }
var diff_matrix = Array(m + 1) { IntArray(n + 1) }
var sum_matrix = Array(m + 1) { IntArray(n + 1) }
for (i in 0..<m) {
for (j in 0..<n) {
prefix_sums_matrix[i + 1][j + 1] =
prefix_sums_matrix[i + 1][j] +
prefix_sums_matrix[i][j + 1] -
prefix_sums_matrix[i][j] +
grid[i][j]
}
}
for (i in 0..<m) {
for (j in 0..<n) {
if (grid[i][j] != 0) {
continue
}
val bottom = i + stampHeight
val right = j + stampWidth
if (bottom > m || right > n) {
continue
}
val sum = prefix_sums_matrix[bottom][right] -
prefix_sums_matrix[bottom][j] -
prefix_sums_matrix[i][right] +
prefix_sums_matrix[i][j]
if (sum == 0) {
diff_matrix[i][j] += 1
diff_matrix[bottom][right] += 1
diff_matrix[i][right] -= 1
diff_matrix[bottom][j] -= 1
}
}
}
for (i in 0..<m) {
for (j in 0..<n) {
if (grid[i][j] != 0) {
continue
}
val sum = sum_matrix[i][j + 1] +
sum_matrix[i + 1][j] -
sum_matrix[i][j] +
diff_matrix[i][j]
if (sum == 0) {
return false
}
sum_matrix[i + 1][j + 1] = sum
}
}
return true
}
}impl Solution {
pub fn possible_to_stamp(grid: Vec<Vec<i32>>, stamp_height: i32, stamp_width: i32) -> bool {
let n: usize = grid.len();
let m: usize = grid[0].len();
let mut prefix_vec: Vec<Vec<i32>> = vec![vec![0; m + 1]; n + 1];
// Initialize the prefix vector
for i in 0..n {
for j in 0..m {
prefix_vec[i + 1][j + 1] =
prefix_vec[i][j + 1] + prefix_vec[i + 1][j] - prefix_vec[i][j] + grid[i][j];
}
}
let mut diff_vec: Vec<Vec<i32>> = vec![vec![0; m + 1]; n + 1];
// Construct the difference vector based on prefix sum vector
for i in 0..n {
for j in 0..m {
// If the value of the cell is one, just bypass this
if grid[i][j] == 1 {
continue;
}
// Otherwise, try stick the stamp
let x: usize = i + (stamp_height as usize);
let y: usize = j + (stamp_width as usize);
// Check the bound
if x <= n && y <= m {
// If the region can be sticked (All cells are empty, which means the sum will be zero)
if prefix_vec[x][y] - prefix_vec[x][j] - prefix_vec[i][y] + prefix_vec[i][j]
== 0
{
// Update the difference vector
diff_vec[i][j] += 1;
diff_vec[x][y] += 1;
diff_vec[x][j] -= 1;
diff_vec[i][y] -= 1;
}
}
}
}
let mut check_vec: Vec<Vec<i32>> = vec![vec![0; m + 1]; n + 1];
// Check the prefix sum of difference vector, to determine if there is any empty cell left
for i in 0..n {
for j in 0..m {
// If the value of the cell is one, just bypass this
if grid[i][j] == 1 {
continue;
}
// Otherwise, check if the region is empty, by calculating the prefix sum of difference vector
check_vec[i + 1][j + 1] =
check_vec[i][j + 1] + check_vec[i + 1][j] - check_vec[i][j] + diff_vec[i][j];
if check_vec[i + 1][j + 1] == 0 {
return false;
}
}
}
true
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Stamping the Grid easy or hard?
Stamping the Grid is classified as a Hard problem on LeetCode because it combines multiple advanced concepts: 2D prefix sums, greedy placement logic, and difference arrays. Recognizing that brute-force placement is unnecessary is the main challenge.
Stamping the Grid Python/Java solution
Python and C++ implementations typically follow the prefix-sum greedy approach: compute prefix sums, detect valid stamp placements, mark coverage using a difference grid, and finally validate each empty cell. JavaScript solutions can also be implemented but are sometimes shown with a simpler backtracking demonstration.
How to solve Stamping the Grid in O(m*n)?
Precompute a 2D prefix sum of the grid so you can check whether any stamp-sized rectangle contains a blocked cell in O(1). For every valid placement, update a difference matrix marking the region covered by that stamp. After converting the difference matrix to actual coverage counts, verify each zero cell has coverage greater than zero.
What is the best approach for Stamping the Grid?
The optimal solution uses a greedy strategy combined with a 2D prefix sum and a difference array. Prefix sums allow constant-time checks to see if a stamp-sized rectangle contains blocked cells. Valid placements are recorded using a difference grid, and a final prefix pass confirms every empty cell is covered. This runs in O(m*n) time.
Is Stamping the Grid asked at Google/Amazon/Meta?
Grid prefix sum and matrix coverage problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test rectangle queries, range updates, and greedy reasoning on matrices.
What data structure is used in Stamping the Grid?
The main data structures are a 2D prefix sum array and a 2D difference array. Prefix sums allow constant-time rectangle sum queries, while the difference array efficiently records stamp coverage over rectangular regions.
What is the time complexity of Stamping the Grid?
The optimal algorithm runs in O(m*n) time where m and n are the grid dimensions. It performs a few linear scans: building a prefix sum, evaluating all stamp placements, and computing coverage. Space complexity is also O(m*n) for the prefix and difference arrays.