MaximumSideLengthofASquareWithSumLessThanOrEqualToThreshold.java

public int maxSideLength(int[][] mat, int threshold) {
    if (mat == null || mat.length == 0 || mat[0].length == 0) {
        return 0;
    }
    int row = mat.length;
    int col = mat[0].length;
    // easier to implement with the initial value on the boarder to be 0
    int[][] prefixSum = new int[row + 1][col + 1];  

    // the idea of using a prefix sum matrix should be a common technique, each cell contains the sum of
    // its top left sum, including itself
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + mat[i - 1][j - 1]; // needs to plus itself as well
        }
    }

    // brute force way to start from max length O(M*N*min(M, N))= O(N^3)
    // could use binary search to find the first element
    // https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/discuss/451871/Java-sum%2Bbinary-O(m*n*log(min(mn)))-or-sum%2Bsliding-window-O(m*n)
    for (int len = Math.min(row, col); len >= 1; len--) {
        for (int i = 1; i + len <= row; i++) {
            for (int j = 1; j + len <= col; j++) {
                if (prefixSum[i + len][j + len] - prefixSum[i - 1][j + len] - prefixSum[i + len][j - 1] + prefixSum[i - 1][j - 1] <= threshold) {
                    return len + 1;
                }
            }
        }
    }

    return 0;
}