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