LeetCode Entry

3212. Count Submatrices With Equal Frequency of X and Y

19.03.2026 medium 2026 kotlin rust

Count prefix freq X == freq Y

3212. Count Submatrices With Equal Frequency of X and Y medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1302

Problem TLDR

Count prefix freq X == freq Y #medium #matrix

Intuition

Keep two prefixes: for the X and for the Y. Freq = freq_left + freq_top

Approach

• we can just look at balance x++ y–
• we can store just the last row
• to keep track ‘at least one’ rule, use a single bit per column

Complexity

• Time complexity: \(O(nm)\)

• Space complexity: \(O(m)\)

Code

// 18ms
    fun numberOfSubmatrices(g: Array<CharArray>) =
        IntArray(g[0].size).let { X ->
            g.sumOf { r ->
                var x = 0; var s = 0; var j = 0
                r.count { c ->
                    if (c > '.') { s = 1; x += 4*(c - 'X')-2 }
                    X[j] = X[j] + x or s; X[j++] == 1
                }
            }
        }

// 18ms
    pub fn number_of_submatrices(g: Vec<Vec<char>>) -> i32 {
        let mut v = vec![0; g[0].len()];
        g.iter().map(|r| {
            let (mut b, mut s) = (0, 0);
            r.iter().zip(&mut v).map(|(&c, x)| {
                if c > '.' { s = 1; b += (c as i32 - 88)*4-2 }
                *x = *x + b|s; (*x == 1) as i32
            }).sum::<i32>()
        }).sum()
    }