In this guide, you will get 2132. Stamping the Grid LeetCode Solution with the best time and space complexity. The solution to Stamping the Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
2132. Stamping the Grid LeetCode Solution in C++
class Solution {
public:
bool possibleToStamp(vector<vector<int>>& grid, int stampHeight,
int stampWidth) {
const int m = grid.size();
const int n = grid[0].size();
// A[i][j] := the number of 1s in grid[0..i)[0..j)
vector<vector<int>> A(m + 1, vector<int>(n + 1));
// B[i][j] := the number of ways to stamp the submatrix in [0..i)[0..j)
vector<vector<int>> B(m + 1, vector<int>(n + 1));
// fit[i][j] := true if the stamps can fit with the right-bottom at (i, j)
vector<vector<bool>> fit(m, vector<bool>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + grid[i][j];
if (i + 1 >= stampHeight && j + 1 >= stampWidth) {
const int x = i - stampHeight + 1;
const int y = j - stampWidth + 1;
if (A[i + 1][j + 1] - A[x][j + 1] - A[i + 1][y] + A[x][y] == 0)
fit[i][j] = true;
}
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + fit[i][j];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (!grid[i][j]) {
const int x = min(i + stampHeight, m);
const int y = min(j + stampWidth, n);
if (B[x][y] - B[i][y] - B[x][j] + B[i][j] == 0)
return false;
}
return true;
}
}; /* code provided by PROGIEZ */
2132. Stamping the Grid LeetCode Solution in Java
class Solution {
public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
final int m = grid.length;
final int n = grid[0].length;
// A[i][j] := the number of 1s in grid[0..i)[0..j)
int[][] A = new int[m + 1][n + 1];
// B[i][j] := the number of ways to stamp the submatrix in [0..i)[0..j)
int[][] B = new int[m + 1][n + 1];
// fit[i][j] := 1 if the stamps can fit with the right-bottom at (i, j)
int[][] fit = new int[m][n];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + grid[i][j];
if (i + 1 >= stampHeight && j + 1 >= stampWidth) {
final int x = i - stampHeight + 1;
final int y = j - stampWidth + 1;
if (A[i + 1][j + 1] - A[x][j + 1] - A[i + 1][y] + A[x][y] == 0)
fit[i][j] = 1;
}
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + fit[i][j];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 0) {
final int x = Math.min(i + stampHeight, m);
final int y = Math.min(j + stampWidth, n);
if (B[x][y] - B[i][y] - B[x][j] + B[i][j] == 0)
return false;
}
return true;
}
} // code provided by PROGIEZ
2132. Stamping the Grid LeetCode Solution in Python
class Solution:
def possibleToStamp(
self,
grid: list[list[int]],
stampHeight: int,
stampWidth: int,
) -> bool:
m = len(grid)
n = len(grid[0])
# A[i][j] := the number of 1s in grid[0..i)[0..j)
A = [[0] * (n + 1) for _ in range(m + 1)]
# B[i][j] := the number of ways to stamp the submatrix in [0..i)[0..j)
B = [[0] * (n + 1) for _ in range(m + 1)]
# fit[i][j] := true if the stamps can fit with the right-bottom at (i, j)
fit = [[False] * n for _ in range(m)]
for i in range(m):
for j in range(n):
A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + grid[i][j]
if i + 1 >= stampHeight and j + 1 >= stampWidth:
x = i - stampHeight + 1
y = j - stampWidth + 1
if A[i + 1][j + 1] - A[x][j + 1] - A[i + 1][y] + A[x][y] == 0:
fit[i][j] = True
for i in range(m):
for j in range(n):
B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + fit[i][j]
for i in range(m):
for j in range(n):
if not grid[i][j]:
x = min(i + stampHeight, m)
y = min(j + stampWidth, n)
if B[x][y] - B[i][y] - B[x][j] + B[i][j] == 0:
return False
return True # code by PROGIEZ
