LeetCode Entry

3070. Count Submatrices with Top-Left Element and Sum Less Than k

18.03.2026 medium 2026 kotlin rust

Count prefix sums less than K

3070. Count Submatrices with Top-Left Element and Sum Less Than k medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1301

Problem TLDR

Count prefix sums less than K #medium #matrix

Intuition

Just compute and re-use prefix sum.

Approach

• count in-place
• use row-sum extra variable
• rust itertools have product!
• optimization: after sum bigger than k consider this as the limit for x

Complexity

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

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

Code

// 39ms
    fun countSubmatrices(g: Array<IntArray>, k: Int) =
        g.indices.sumOf { y -> g[0].indices.count { x ->
            g[y][x] += (if (y > 0) g[y-1][x] else 0) +
                        (if (x > 0) g[y][x-1] else 0) -
                        (if (x*y > 0) g[y-1][x-1] else 0)
            g[y][x] <= k
        }}

// 0ms
    pub fn count_submatrices(mut g: Vec<Vec<i32>>, k: i32) -> i32 {
        (0..g.len()).map(|y| (0..g[0].len()).fold((0,0), |(mut s, c), x| {
            s += g[y][x]; g[y][x] = s + (y>0) as i32 * g[y.max(1)-1][x];
            (s, c + (g[y][x] <= k) as i32)
        }).1).sum()
    }