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.

&nbsp;
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


&nbsp;
Constraints:


	m == mat.length
	n == mat[i].length
	1 &lt;= m, n &lt;= 300
	0 &lt;= mat[i][j] &lt;= 104
	0 &lt;= threshold &lt;= 105


class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        # prefix matrix
        dp = [[0]*(len(mat[0])+1) for _ in range(len(mat)+1)]
        
        for i in range(1, len(mat)+1):
            for j in range(1, len(mat[0])+1):
                dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i-1][j-1]
                       
        #bin search
        max_side = 0
        for i in range(1, len(mat) + 1):
            for j in range(1, len(mat[0]) + 1):
                if min(i, j) < max_side:
                    continue
                left = 0
                right = min(i,j)
                while left <= right:
                    mid = (left+right)//2
                    pref_sum = dp[i][j] - dp[i-mid][j] - dp[i][j-mid] + dp[i-mid][j-mid]
                    if pref_sum <= threshold:
                        max_side = max(max_side, mid)
                        left = mid + 1
                    else:
                        right = mid - 1
        return max_side
                    
class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int rows = mat.length;
        int cols = mat[0].length;
        int[][] preSum = new int[rows+1][cols+1];
        for(int i=1;i<=rows;i++){
            for(int j=1;j<=cols;j++){
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + mat[i-1][j-1];
            }
        }
        int lo=1,hi=Math.min(rows,cols);
        while(lo<=hi){
            int m = (lo+hi)>>1;
            if(fun(preSum,threshold,rows,cols,m)) lo=m+1;
            else hi=m-1;
        }
        return lo-1;
    }
    private boolean fun(int[][] preSum, int maxSum,int rows, int cols, int size){
        for(int r=size;r<=rows;r++){
            for(int c=size;c<=cols;c++){
                int sum = preSum[r][c] - preSum[r-size][c] - preSum[r][c-size] + preSum[r-size][c-size];
                if(sum <= maxSum) return true;
            }
        }
        return false;
    }
}
class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size();
        int n = mat[0].size();
        
        int least = min (m,n);
        
        vector<vector<int>> dp (m+1, vector<int> (n+1, 0));
        
        /*
        create dp matrix with sum of all squares
        so for the following input matrix
         1 1 1 1
         1 0 0 0
         1 0 0 0
         1 0 0 0
         
        m = 4; n = 4; least = 4; threshold = 6
        you get the dp matrix to be:
         0 0 0 0 0
         0 1 2 3 4
         0 2 3 4 5
         0 3 4 5 6
         0 4 5 6 7
        */
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i+1][j+1] = mat[i][j] + dp[i+1][j] + dp[i][j+1] - dp[i][j];
            }
        }
        
        int sum = 0;
        
        /*
        from the previous example the once we start looking from least = 4 to see if the sum is less than threshold
        for least = 4; sum = 7 - 0 - 0 + 0. (looking at the full 4 x 4 matrix) 7 is > threshold.. so keep looking..
        for least = 3; sum = 5 - 0 - 0 + 0. (looking at the 3 x 3 matrix) .. 5 < threshold.. return 3.
        
        say if the threshold was lower e.g. threshold = 2?
        continuing...
        for least = 3; sum = 6 - 3 - 0 + 0 = 3.
        for least = 3; sum = 6 - 0 - 3 + 0 = 3;
        for least = 3; sum = 7 - 4 - 4 + 1 = 0;
        
        */
        
        for(int k = least; k > 0; k--) {
            for(int i = k; i < m+1; i++) {
                for(int j = k; j < n+1; j++) {
                    sum = dp[i][j] - dp[i-k][j] - dp[i][j-k] + dp[i-k][j-k];
                    if(sum <= threshold) {
                        return k;
                    }
                }
            }
        }
        
        return 0;
    }
};
/**
 * @param {number[][]} mat
 * @param {number} threshold
 * @return {number}
 */
var maxSideLength = function(mat, threshold) {
    const n = mat.length, m = mat[0].length;
    
    // build sum matrix
    let sum = [];
    for(let i=0; i<=n; i++) {
        sum.push(new Array(m+1).fill(0));
        for(let j=0; j<=m; j++) {
            if(i==0 || j==0) {
                continue;
            }
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mat[i-1][j-1];
        }
    }
    
    // function to check square sum <= threshold
    const underThreshold = function(len) {
        for(let i=len; i<=n; i++) {
            for(let j=len; j<=m; j++) {
                if(sum[i][j] - sum[i-len][j] - sum[i][j-len] + sum[i-len][j-len] <= threshold) {
                    return true;
                }
            }
        }
        return false;
    };
    
    // binary search
    let l=0, r=Math.min(n, m);
    while(l<=r) {
        const mid = Math.floor((l+r)/2);
        if(underThreshold(mid)) {
            l = mid+1;
        } else {
            r = mid-1;
        }
    }
    return r;
};
Maximum Side Length of a Square with Sum Less than or Equal to Threshold