Count square submatrices with all ones

Array Dynamic Programming Matrix

80.7% acceptance

Feb 25, 2026

5937

117

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_squares(mut matrix: Vec<Vec<i32>>) -> i32 {
    let m = matrix.len();
    let n = matrix[0].len();
    let mut ans = 0;

    for i in 0..m {
      for j in 0..n {
        if matrix[i][j] == 1 && i > 0 && j > 0 {
          matrix[i][j] = matrix[i-1][j].min(matrix[i][j-1]).min(matrix[i-1][j-1]) + 1;
        }
        ans += matrix[i][j];
      }
    }
    ans
  }
}