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 <= 300m == mat.lengthn == mat[i].length0 <= mat[i][j] <= 100000 <= 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;
}
};
Solution 2. Binary Answer
// 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 }