##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1292.html

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

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

Related Topics:
Array, Binary Search

## Solution 1. Prefix Sum

// OJ: https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int maxSideLength(vector<vector<int>>& A, int threshold) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<vector<int>> sum(M + 1, vector<int>(N + 1));
for (int i = 0; i < M; ++i) {
int s = 0;
for (int j = 0; j < N; ++j) sum[i + 1][j + 1] = sum[i][j + 1] + (s += A[i][j]);
}
for (int i = 0; ans <= min(M, N) && i <= M - ans; ++i) {
for (int j = 0; ans <= min(M, N) && j <= N - ans; ++j) {
for (; ans <= min(M - i, N - j) && sum[i + ans][j + ans] - sum[i + ans][j] - sum[i][j + ans] + sum[i][j] <= threshold; ++ans);
}
}
return ans - 1;
}
};


// OJ: https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/
// Time: O(MN * log(min(M, N)))
// Space: O(MN)
class Solution {
bool valid(vector<vector<int>> &sum, int len, int threshold) {
for (int i = 0; i < sum.size() - len; ++i) {
for (int j = 0; j < sum[0].size() - len; ++j) {
if (sum[i + len][j + len] - sum[i + len][j] - sum[i][j + len] + sum[i][j] <= threshold) return true;
}
}
return false;
}
public:
int maxSideLength(vector<vector<int>>& A, int threshold) {
int M = A.size(), N = A[0].size(), L = 0, R = min(M, N);
vector<vector<int>> sum(M + 1, vector<int>(N + 1));
for (int i = 0; i < M; ++i) {
int s = 0;
for (int j = 0; j < N; ++j) sum[i + 1][j + 1] = sum[i][j + 1] + (s += A[i][j]);
}
while (L <= R) {
int M = (L + R) / 2;
if (valid(sum, M, threshold)) L = M + 1;
else R = M - 1;
}
return R;
}
};

• class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int rows = mat.length, columns = mat[0].length;
int maxSideLength = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
int maxSide = Math.min(rows - i, columns - j);
int sum = mat[i][j];
if (sum > threshold)
break;
maxSideLength = Math.max(maxSideLength, 1);
for (int k = 2; k <= maxSide; k++) {
int nextRowIndex = i + k - 1, nextColumnIndex = j + k - 1;
for (int m = j; m < nextColumnIndex; m++)
sum += mat[nextRowIndex][m];
for (int m = i; m < nextRowIndex; m++)
sum += mat[m][nextColumnIndex];
sum += mat[nextRowIndex][nextColumnIndex];
if (sum <= threshold)
maxSideLength = Math.max(maxSideLength, k);
}
}
}
return maxSideLength;
}
}

############

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

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

• // OJ: https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int maxSideLength(vector<vector<int>>& A, int threshold) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<vector<int>> sum(M + 1, vector<int>(N + 1));
for (int i = 0; i < M; ++i) {
int s = 0;
for (int j = 0; j < N; ++j) sum[i + 1][j + 1] = sum[i][j + 1] + (s += A[i][j]);
}
for (int i = 0; ans <= min(M, N) && i <= M - ans; ++i) {
for (int j = 0; ans <= min(M, N) && j <= N - ans; ++j) {
for (; ans <= min(M - i, N - j) && sum[i + ans][j + ans] - sum[i + ans][j] - sum[i][j + ans] + sum[i][j] <= threshold; ++ans);
}
}
return ans - 1;
}
};

• class Solution:
def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
m, n = len(mat), len(mat[0])
s = [[0] * 310 for _ in range(310)]
for i in range(m):
for j in range(n):
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j]

def check(l):
for i in range(m):
for j in range(n):
if i + l - 1 < m and j + l - 1 < n:
i1, j1 = i + l - 1, j + l - 1
t = s[i1 + 1][j1 + 1] - s[i1 + 1][j] - s[i][j1 + 1] + s[i][j]
if t <= threshold:
return True
return False

left, right = 0, min(m, n)
while left < right:
mid = (left + right + 1) >> 1
if check(mid):
left = mid
else:
right = mid - 1
return left


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

func min(a, b int) int {
if a < b {
return a
}
return b
}