Maximum Side Length of a Square with Sum Less than or Equal to Threshold
Medium
Provided a m x n matrix mat and an integer threshold, produce the maximum side-length of a square with a sum less than or equal to threshold or produce 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 or equal to 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] <= 10^40 <= threshold <= 10^5
Did this problem appear in one of your interviews?
Responses stay private.