# 2132. Stamping the Grid

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public: bool possibleToStamp(vector>& 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> A(m + 1, vector(n + 1)); // B[i][j] := # of ways to stamp the submatrix in [0..i)[0..j) vector> B(m + 1, vector(n + 1)); // fit[i][j] := true if the stamps can fit with right-bottom at (i, j) vector> fit(m, vector(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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 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