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

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: int maxSideLength(vector>& mat, int threshold) { const int m = mat.size(); const int n = mat[0].size(); int ans = 0; vector> prefix(m + 1, vector(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>& 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]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 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]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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