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.lengthn == mat[i].length1 <= m, n <= 3000 <= mat[i][j] <= 1040 <= threshold <= 105This approach involves calculating the prefix sum matrix which allows for constant time computation of any sub-matrix sum. We then iterate over possible top-left corners for squares and check if the sum of the square area does not exceed the threshold using the prefix sum matrix.
This solution computes a prefix sum matrix of size (m+1)x(n+1). It then iterates over each possible starting point and potential square sizes contained within the matrix. The prefixed summed values allow for rapid calculation of the sum for any rectilinear sub-section of the matrix.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m*n*k) where k is constrained by min(m, n) and bounded by the success of squares.
Space Complexity: O(m*n)
This approach utilizes binary search to find the maximum possible size of a square whose sum does not exceed the given threshold. It initially calculates a prefix sum matrix and then performs binary search based on potential square side lengths.
This C implementation uses a binary search on the possible side lengths to efficiently determine if a square of that side can have a sum less than or equal to the threshold. The helper function isValid checks if the sum of the square area from the prefix sum matrix fits within the given threshold.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m*n*log(min(m, n)))
Space Complexity: O(m*n)
| Approach | Complexity |
|---|---|
| Using Prefix Sum and Iteration | Time Complexity: O(m*n*k) where k is constrained by min(m, n) and bounded by the success of squares. |
| Binary Search on Side Length | Time Complexity: O(m*n*log(min(m, n))) |
Maximal Square - Top Down Memoization - Leetcode 221 • NeetCode • 83,339 views views
Watch 9 more video solutions →Practice Maximum Side Length of a Square with Sum Less than or Equal to Threshold with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor