Maximum side length of a square with sum less than or equal to threshold

Array Binary Search Matrix Prefix Sum

65.4% acceptance

Feb 25, 2026

1539

124

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_side_length(mat: Vec<Vec<i32>>, threshold: i32) -> i32 {
    let m = mat.len();
    let n = mat[0].len();
    // Build 2D prefix sum
    let mut prefix = vec![vec![0i64; n + 1]; m + 1];
    for i in 1..=m {
      for j in 1..=n {
        prefix[i][j] = mat[i-1][j-1] as i64
          + prefix[i-1][j]
          + prefix[i][j-1]
          - prefix[i-1][j-1];
      }
    }
    let query = |r1: usize, c1: usize, r2: usize, c2: usize| -> i64 {
      prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]
    };
    let mut ans = 0i32;
    for k in 1..=m.min(n) {
      let mut found = false;
      'outer: for i in k..=m {
        for j in k..=n {
          if query(i - k + 1, j - k + 1, i, j) <= threshold as i64 {
            found = true;
            break 'outer;
          }
        }
      }
      if found {
        ans = k as i32;
      } else {
        break;
      }
    }
    ans
  }
}