# 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

## Description

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


Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 300
• 0 <= mat[i][j] <= 104
• 0 <= threshold <= 105

## Solutions

• class Solution {
private int m;
private int n;
private int threshold;
private int[][] s;

public int maxSideLength(int[][] mat, int threshold) {
m = mat.length;
n = mat[0].length;
this.threshold = threshold;
s = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int l = 0, r = Math.min(m, n);
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}

private boolean check(int k) {
for (int i = 0; i < m - k + 1; ++i) {
for (int j = 0; j < n - k + 1; ++j) {
if (s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] <= threshold) {
return true;
}
}
}
return false;
}
}

• class Solution {
public:
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat[0].size();
int s[m + 1][n + 1];
memset(s, 0, sizeof(s));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
auto check = [&](int k) {
for (int i = 0; i < m - k + 1; ++i) {
for (int j = 0; j < n - k + 1; ++j) {
if (s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] <= threshold) {
return true;
}
}
}
return false;
};
int l = 0, r = min(m, n);
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};

• class Solution:
def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
def check(k: int) -> bool:
for i in range(m - k + 1):
for j in range(n - k + 1):
v = s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j]
if v <= threshold:
return True
return False

m, n = len(mat), len(mat[0])
s = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(mat, 1):
for j, x in enumerate(row, 1):
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x
l, r = 0, min(m, n)
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return l


• func maxSideLength(mat [][]int, threshold int) int {
m, n := len(mat), len(mat[0])
s := make([][]int, m+1)
for i := range s {
s[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1]
}
}
check := func(k int) bool {
for i := 0; i < m-k+1; i++ {
for j := 0; j < n-k+1; j++ {
if s[i+k][j+k]-s[i][j+k]-s[i+k][j]+s[i][j] <= threshold {
return true
}
}
}
return false
}
l, r := 0, min(m, n)
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
return l
}

• function maxSideLength(mat: number[][], threshold: number): number {
const m = mat.length;
const n = mat[0].length;
const s: number[][] = Array(m + 1)
.fill(0)
.map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
const check = (k: number): boolean => {
for (let i = 0; i < m - k + 1; ++i) {
for (let j = 0; j < n - k + 1; ++j) {
if (s[i + k][j + k] - s[i + k][j] - s[i][j + k] + s[i][j] <= threshold) {
return true;
}
}
}
return false;
};

let l = 0;
let r = Math.min(m, n);
while (l < r) {
const mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}