#3212
Medium Algorithms Count submatrices with equal frequency of x and y
Array Matrix Prefix Sum
51.5% acceptance
Feb 25, 2026
161
27
Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.',
return the number of submatrices that contain:
grid[0][0]
an equal frequency of 'X' and 'Y'.
at least one 'X'.
Solution
Rust
Time O(n * m)
Space O(n * m)
impl Solution {
pub fn number_of_submatrices(grid: Vec<Vec<char>>) -> i32 {
let rows = grid.len();
let cols = grid[0].len();
// 2D prefix sums for X count and Y count
let mut px = vec![vec![0i32; cols + 1]; rows + 1];
let mut py = vec![vec![0i32; cols + 1]; rows + 1];
let mut count = 0i32;
for i in 1..=rows {
for j in 1..=cols {
let xval = if grid[i - 1][j - 1] == 'X' { 1 } else { 0 };
let yval = if grid[i - 1][j - 1] == 'Y' { 1 } else { 0 };
px[i][j] = px[i - 1][j] + px[i][j - 1] - px[i - 1][j - 1] + xval;
py[i][j] = py[i - 1][j] + py[i][j - 1] - py[i - 1][j - 1] + yval;
if px[i][j] > 0 && px[i][j] == py[i][j] {
count += 1;
}
}
}
count
}
}