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.
Example 1:
Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 Output: 2 Explanation: The maximum side length of square with sum less than 4 is 2 as shown.
Example 2:
Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1 Output: 0
Example 3:
Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6 Output: 3
Example 4:
Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184 Output: 2
Constraints:
1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5
struct Solution;
impl Solution {
fn max_side_length(mat: Vec<Vec<i32>>, threshold: i32) -> i32 {
let n = mat.len();
let m = mat[0].len();
let mut prefix = vec![vec![0; m + 1]; n + 1];
let mut k = 1;
for i in 0..n {
for j in 0..m {
prefix[i][j] = mat[i][j];
if i > 0 {
prefix[i][j] += prefix[i - 1][j];
}
if j > 0 {
prefix[i][j] += prefix[i][j - 1];
}
if i > 0 && j > 0 {
prefix[i][j] -= prefix[i - 1][j - 1];
}
if i >= k - 1 && j >= k - 1 {
let mut sum = prefix[i][j];
if i >= k {
sum -= prefix[i - k][j];
}
if j >= k {
sum -= prefix[i][j - k];
}
if i >= k && j >= k {
sum += prefix[i - k][j - k];
}
if sum <= threshold {
k += 1;
}
}
}
}
(k - 1) as i32
}
}
#[test]
fn test() {
let mat = vec_vec_i32![
[1, 1, 3, 2, 4, 3, 2],
[1, 1, 3, 2, 4, 3, 2],
[1, 1, 3, 2, 4, 3, 2]
];
let threshold = 4;
let res = 2;
assert_eq!(Solution::max_side_length(mat, threshold), res);
let mat = vec_vec_i32![
[2, 2, 2, 2, 2],
[2, 2, 2, 2, 2],
[2, 2, 2, 2, 2],
[2, 2, 2, 2, 2],
[2, 2, 2, 2, 2]
];
let threshold = 1;
let res = 0;
assert_eq!(Solution::max_side_length(mat, threshold), res);
let mat = vec_vec_i32![[1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]];
let threshold = 6;
let res = 3;
assert_eq!(Solution::max_side_length(mat, threshold), res);
let mat = vec_vec_i32![
[18, 70],
[61, 1],
[25, 85],
[14, 40],
[11, 96],
[97, 96],
[63, 45]
];
let threshold = 40184;
let res = 2;
assert_eq!(Solution::max_side_length(mat, threshold), res);
}