Skip to content

3212. Count Submatrices With Equal Frequency of X and Y

Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of

submatrices

that contains:

  • grid[0][0]
  • an equal frequency of 'X' and 'Y'.
  • at least one 'X'.

Example 1:

Input: grid = [["X","Y","."],["Y",".","."]]

Output: 3

Explanation:

img

Example 2:

Input: grid = [["X","X"],["X","Y"]]

Output: 0

Explanation:

No submatrix has an equal frequency of 'X' and 'Y'.

Example 3:

Input: grid = [[".","."],[".","."]]

Output: 0

Explanation:

No submatrix has at least one 'X'.

Constraints:

  • 1 <= grid.length, grid[i].length <= 1000
  • grid[i][j] is either 'X', 'Y', or '.'.

Solution:

class Solution {
    public int numberOfSubmatrices(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] prefixX = new int[m + 1][n + 1];
        int[][] prefixY = new int[m + 1][n + 1];

        // Compute prefix sums
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixX[i][j] = prefixX[i - 1][j] + prefixX[i][j - 1] - prefixX[i - 1][j - 1];
                prefixY[i][j] = prefixY[i - 1][j] + prefixY[i][j - 1] - prefixY[i - 1][j - 1];

                if (grid[i - 1][j - 1] == 'X') {
                    prefixX[i][j]++;
                } else if (grid[i - 1][j - 1] == 'Y') {
                    prefixY[i][j]++;
                }
            }
        }

        int count = 0;

        // Check each possible submatrix starting from (0,0) to (i,j)
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int numX = prefixX[i][j];
                int numY = prefixY[i][j];

                if (numX == numY && numX > 0) {
                    count++;
                }
            }
        }

        return count;
    }
}