• Time:O(mn)
• Space:O(mn)

## 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] := # of 1s in grid[0..i)[0..j)
vector<vector<int>> A(m + 1, vector<int>(n + 1));
// B[i][j] := # 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 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;
}
};
``````

## 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] := # of 1s in grid[0..i)[0..j)
int[][] A = new int[m + 1][n + 1];
// B[i][j] := # 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 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;
}
}
``````

## 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] := # of 1s in grid[0..i)[0..j)
A = [[0] * (n + 1) for _ in range(m + 1)]
# B[i][j] := # 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 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
``````