1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold LeetCode Solution
In this guide, you will get 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold LeetCode Solution with the best time and space complexity. The solution to Maximum Side Length of a Square with Sum Less than or Equal to Threshold problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Complexity Analysis
Time Complexity:
Space Complexity:
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold LeetCode Solution in C++
class Solution {
public:
int maxSideLength(vector<vector<int>>& mat, int threshold) {
const int m = mat.size();
const int n = mat[0].size();
int ans = 0;
vector<vector<int>> prefix(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
prefix[i + 1][j + 1] =
mat[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
for (int length = ans; length < min(m - i, n - j); ++length) {
if (squareSum(prefix, i, j, i + length, j + length) > threshold)
break;
ans = max(ans, length + 1);
}
return ans;
}
private:
int squareSum(vector<vector<int>>& prefix, int r1, int c1, int r2, int c2) {
return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] +
prefix[r1][c1];
}
}; /* code provided by PROGIEZ */
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold LeetCode Solution in Java
class Solution {
public int maxSideLength(int[][] mat, int threshold) {
final int m = mat.length;
final int n = mat[0].length;
int ans = 0;
int[][] prefix = new int[m + 1][n + 1];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
prefix[i + 1][j + 1] = mat[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
for (int length = ans; length < Math.min(m - i, n - j); ++length) {
if (squareSum(prefix, i, j, i + length, j + length) > threshold)
break;
ans = Math.max(ans, length + 1);
}
return ans;
}
private int squareSum(int[][] prefix, int r1, int c1, int r2, int c2) {
return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1];
}
} // code provided by PROGIEZ
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold LeetCode Solution in Python
class Solution:
def maxSideLength(self, mat: list[list[int]], threshold: int) -> int:
m = len(mat)
n = len(mat[0])
ans = 0
prefix = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
prefix[i + 1][j + 1] = (mat[i][j] + prefix[i][j + 1] +
prefix[i + 1][j] - prefix[i][j])
def squareSum(r1: int, c1: int, r2: int, c2: int) -> int:
return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1]
for i in range(m):
for j in range(n):
for length in range(ans, min(m - i, n - j)):
if squareSum(i, j, i + length, j + length) > threshold:
break
ans = max(ans, length + 1)
return ans # code by PROGIEZ
