Count submatrices with all ones

Array Dynamic Programming Stack Matrix Monotonic Stack

71.1% acceptance

Feb 25, 2026

2666

220

Given an m x n binary matrix mat, return the number of submatrices that have all ones.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_submat(mat: Vec<Vec<i32>>) -> i32 {
    let m = mat.len();
    let n = mat[0].len();
    // height[j] = consecutive 1s above and including current row at column j
    let mut height = vec![0i32; n];
    let mut ans = 0;
    for i in 0..m {
      for j in 0..n {
        height[j] = if mat[i][j] == 1 { height[j] + 1 } else { 0 };
      }
      // For each column j as right boundary, sweep left counting rectangles
      for j in 0..n {
        let mut min_h = height[j];
        for k in (0..=j).rev() {
          min_h = min_h.min(height[k]);
          if min_h == 0 { break; }
          ans += min_h;
        }
      }
    }
    ans
  }
}