Skip to content

3212. Count Submatrices With Equal Frequency of X and Y 👍

  • 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
class Solution {
 public:
  int numberOfSubmatrices(vector<vector<char>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    int ans = 0;
    // x[i][j] := the number of 'X' in grid[0..i)[0..j)
    vector<vector<int>> x(m + 1, vector<int>(n + 1));
    // y[i][j] := the number of 'Y' in grid[0..i)[0..j)
    vector<vector<int>> y(m + 1, vector<int>(n + 1));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        x[i + 1][j + 1] =
            (grid[i][j] == 'X' ? 1 : 0) + x[i][j + 1] + x[i + 1][j] - x[i][j];
        y[i + 1][j + 1] =
            (grid[i][j] == 'Y' ? 1 : 0) + y[i][j + 1] + y[i + 1][j] - y[i][j];
        if (x[i + 1][j + 1] > 0 && x[i + 1][j + 1] == y[i + 1][j + 1])
          ++ans;
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int numberOfSubmatrices(char[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int ans = 0;
    // x[i][j] := the number of 'X' in grid[0..i)[0..j)
    int[][] x = new int[m + 1][n + 1];
    // y[i][j] := the number of 'Y' in grid[0..i)[0..j)
    int[][] y = new int[m + 1][n + 1];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        x[i + 1][j + 1] = (grid[i][j] == 'X' ? 1 : 0) + x[i][j + 1] + x[i + 1][j] - x[i][j];
        y[i + 1][j + 1] = (grid[i][j] == 'Y' ? 1 : 0) + y[i][j + 1] + y[i + 1][j] - y[i][j];
        if (x[i + 1][j + 1] > 0 && x[i + 1][j + 1] == y[i + 1][j + 1])
          ++ans;
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def numberOfSubmatrices(self, grid: list[list[str]]) -> int:
    m = len(grid)
    n = len(grid[0])
    ans = 0
    # x[i][j] := the number of 'X' in grid[0..i)[0..j)
    x = [[0] * (n + 1) for _ in range(m + 1)]
    # y[i][j] := the number of 'Y' in grid[0..i)[0..j)
    y = [[0] * (n + 1) for _ in range(m + 1)]

    for i, row in enumerate(grid):
      for j, cell in enumerate(row):
        x[i + 1][j + 1] = (cell == 'X') + x[i][j + 1] + x[i + 1][j] - x[i][j]
        y[i + 1][j + 1] = (cell == 'Y') + y[i][j + 1] + y[i + 1][j] - y[i][j]
        if x[i + 1][j + 1] > 0 and x[i + 1][j + 1] == y[i + 1][j + 1]:
          ans += 1

    return ans