# LC1292 - Maximum Side Length of a Square with Sum Less than or Equal to Threshold
## 二维数组前缀和DP + 线性结构二分查找 （非最优）

class Solution {
    
    /*
    x: the side-length of square
    f(x): if the side-length of square is x, its sum is f(x)
    */
    private int rows;
    private int cols;
    
    public int maxSideLength(int[][] mat, int threshold) {
        // sanity check
        // ...
        rows = mat.length;
        cols = mat[0].length;
        int minL = 0;
        int maxL = Math.min(rows, cols);
        
        PrefixSum prefixSum = new PrefixSum(mat);
        
        while (minL + 1 < maxL) {
            int midL = minL + (maxL - minL) / 2;
            if (canMakeSquareBy(midL, threshold, prefixSum)) {
                minL = midL;
            } else {
                maxL = midL;
            }
        }
        
        if (canMakeSquareBy(maxL, threshold, prefixSum)) {
            return maxL;
        }
        if (canMakeSquareBy(minL, threshold, prefixSum)) {
            return minL;
        }
        return 0;
    }
    
    private boolean canMakeSquareBy(int targetL, int threshold, PrefixSum prefixSum) {
        for (int i = targetL; i <= rows; i++) {
            for (int j = targetL; j <= cols; j++) {
                if (prefixSum.getSumFrom(i, j, targetL) <= threshold) {
                    return true;
                }
            }
        }
        return false;
    }
    
    static class PrefixSum {
        private int[][] prefixSum;

        public PrefixSum(int[][] nums) {
            int rows = nums.length;
            int cols = nums[0].length;

            prefixSum = new int[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++) {
                for (int j = 1; j <= cols; j++) {
                    prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + nums[i - 1][j - 1];
                }
            }
        }

        public int getSumFrom(int x, int y, int length) {
            return prefixSum[x][y] - prefixSum[x - length][y] - prefixSum[x][y - length] + prefixSum[x - length][y - length];
        }
    }
}