Count Submatrices With All Ones LeetCode solution in Rust

1
impl Solution {
2
  pub fn num_submat(mat: Vec<Vec<i32>>) -> i32 {
3
    let (m, n) = (mat.len(), mat[0].len());
4
    let (mut clm, mut row) = (vec![vec![0; n]; m + 1], vec![vec![0; n + 1]; m]);
5

6
    for j in 0..n {
7
      for i in 0..m {
8
        clm[i + 1][j] = mat[i][j] as usize + clm[i][j];
9
      }
10
    }
11

12
    for i in 0..m {
13
      for j in 0..n {
14
        row[i][j + 1] = mat[i][j] as usize + clm[i][j];
15
      }
16
    }
17

18
    let mut ret = 0;
19
    for i in 0..m {
20
      for j in 0..n {
21
        let mut h = m - i;
22
        for k in j..n {
23
          // trying to for a rectangle from [i, j] to [i, k] as base with maximum hight h
24
          while h > 0 && clm[i + h][k] - clm[i][k] < h {
25
            h -= 1;
26
          }
27
          if h == 0 {
28
            break;
29
          }
30
          ret += h; // we could have h rectangles with same base, but different height
31
        }
32
      }
33
    }
34

35
    ret as _
36
  }
37
}