Skip to main content
Back to problems
#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)
LeetCode
solution.rs
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
  }
}