Skip to content

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<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;
  }
};

 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] := 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;
  }
}

 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:
  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