Count submatrices with top left element and sum less than k

Array Matrix Prefix Sum

58.3% acceptance

Feb 25, 2026

164

You are given a 0-indexed integer matrix grid and an integer k. Return the number of submatrices that contain the top-left element of the grid, and have a sum less than or equal to k.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_submatrices(grid: Vec<Vec<i32>>, k: i32) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut prefix = vec![vec![0i64; n + 1]; m + 1];
    let mut ans = 0;
    for i in 0..m {
      for j in 0..n {
        prefix[i+1][j+1] = grid[i][j] as i64 + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j];
        if prefix[i+1][j+1] <= k as i64 { ans += 1; }
      }
    }
    ans
  }
}