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

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`

``````class Solution {
public:
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int res = 0, m = mat.size(), n = mat[0].size();
vector<vector<int>> sums(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
sums[i][j] = mat[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 0; (i + k) <= m && (j + k) <= n; ++k) {
int total = sums[i + k][j + k] - sums[i - 1][j + k] - sums[i + k][j - 1] + sums[i - 1][j - 1];
if (total <= threshold) res = max(res, k + 1);
}
}
}
return res;
}
};
``````

``````class Solution {
public:
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat[0].size(), left = 0, right = min(m, n);
vector<vector<int>> sums(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
sums[i][j] = mat[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
}
}
while (left <= right) {
int mid = left + (right - left) / 2;
if (squareExisted(sums, threshold, mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
bool squareExisted(vector<vector<int>>& sums, int threshold, int len) {
for (int i = len; i < sums.size(); ++i) {
for (int j = len; j < sums[0].size(); ++j) {
if (sums[i][j] - sums[i - len][j] - sums[i][j - len] + sums[i - len][j - len] <= threshold) return true;
}
}
return false;
}
};
``````

``````class Solution {
public:
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int res = 0, m = mat.size(), n = mat[0].size();
vector<vector<int>> sums(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
sums[i][j] = mat[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
if (i - res - 1 >= 0 && j - res - 1 >= 0 && sums[i][j] - sums[i - res - 1][j] - sums[i][j - res - 1] + sums[i - res - 1][j - res - 1] <= threshold) {
++res;
}
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1292

https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/

https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/discuss/452666/Easy-Java-optimized-prefix-sum-one-pass-O(mn)

https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/discuss/451871/Java-sum%2Bbinary-O(m*n*log(min(mn)))-or-sum%2Bsliding-window-O(m*n)

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation