Maximum side length of elements and squares less than or equal to the threshold (source: leetcode)

The maximum side length of an element and a square less than or equal to the threshold （ source ： Power button （LeetCode））

 Give you a size of  m x n  Matrix  mat  And an integer threshold  threshold.

 Please return the maximum side length of the square area where the sum of elements is less than or equal to the threshold ; If there is no such square area , Then return to  0 .

 source ： Power button （LeetCode）

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
 explain ： The sum is less than or equal to  4  The maximum side length of the square is  2, As shown in the figure .

 source ： Power button （LeetCode）

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

 source ： Power button （LeetCode）

Solution 1 ： Dynamic programming

This question gives a m x n A two-dimensional array of and an integer number threshold, Let's return the side length of the largest square , Make the sum of the numbers in the square interval less than or equal to threshold. Such a problem of finding the sum of subintervals of two-dimensional arrays , It is easy to think of the problem of finding the sum of subarrays of a one-dimensional array , By establishing the cumulative sum array, we can quickly find the sum of subarrays of any interval in a one-dimensional array . The same is true for two-dimensional arrays , Two dimensional accumulation and array can be established , Then traverse each square interval , Quickly get the sum of its numbers by accumulating the sum array , Then compare if less than or equal to threshold, Then use its side length to update the result res that will do . The size of the two-dimensional cumulative sum array is larger than the original array 1, In this way, it is convenient to deal with the problem of cross-border , The method of accumulation is the number of the original array corresponding to the current position , Add the numbers above and to the left of the cumulative array , Subtract the number at the top left .

After building the accumulation and array , You can traverse all square intervals . Because only one vertex and side length are needed to uniquely determine a square interval , So you can traverse every position in the array , As the upper left vertex of the square interval , Then traverse all the side lengths that do not cross the boundary , And quickly find the sum of intervals . Note that there are some differences between the method of interval sum and the method of accumulation and array , When the upper left vertex of the square interval is (i, j), Side length is k+1 When , Then the lower right vertex is (i+k, j+k), The calculation method of interval sum is sums[i + k][j + k] - sums[i - 1][j + k] - sums[i + k][j - 1] + sums[i - 1][j - 1], You can compare and calculate the difference between accumulation and array by yourself , And then there's and threshold Comparison of the , If it is less than or equal to threshold, Then use k+1 To update the results res that will do , See code below ：

package com.ice.blindweb;

/* @Auther: sugarice * @Date: 2022/07/24/13:57 * @Description: */

public class main {
    

    public static int maxSideLength(int[][] mat, int threshold) {
    
        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
    
            for (int j = 1; j <= n; j++) {
    
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
        int ans = 0;
        for (int k = 1; k <= Math.min(m, n); k++) {
    
            for (int i = 1; i <= m; i++) {
    
                for (int j = 1; j <= n; j++) {
    
                    if (i - k < 0 || j - k < 0) {
    
                        continue;
                    }
                    int tmp = dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k];
                    if (tmp <= threshold) {
    
                        ans = Math.max(ans, k);
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
    
//  Example  1
        int[][] mat = {
    {
    1, 1, 3, 2, 4, 3, 2}, {
    1, 1, 3, 2, 4, 3, 2}, {
    1, 1, 3, 2, 4, 3, 2}};
        int i = maxSideLength(mat, 4);
        System.out.println(i);

//  Example  2
        int[][] mat1 = {
    {
    2, 2, 2, 2, 2, 2, 2}, {
    2, 2, 2, 2, 2, 2, 2}, {
    2, 2, 2, 2, 2, 2, 2}};
        int j = maxSideLength(mat1, 1);
        System.out.println(j);
        
    }
}

Solution 2 ： Dynamic programming + Two points search

Because the maximum side length required has a range , The minimum is 0, No more than m and n The smaller of , Then you can use the binary search method to increase the search speed . You still need to establish accumulation and array sums, Then you can start the binary search , Using sub functions as judgment relations （ Usually by mid calculated ）. The subfunction of judgment is actually to find out whether there is a square interval with a given side length in the whole array , Make the sum of numbers less than or equal to threshold. Because at this time, the side length is determined , Just traverse the position of the upper left vertex , Then quickly calculate the interval sum through accumulation and array to judge , See code below ：

package com.ice.blindweb;

/* @Auther: sugarice * @Date: 2022/07/24/14:22 * @Description: */

public class main1 {
    
    private static int m, n;

    public static int maxSideLength(int[][] mat, int threshold) {
    
        m = mat.length;
        n = mat[0].length;
        int left = 0;
        int right = Math.min(m, n);
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
    
            for (int j = 1; j <= n; j++) {
    
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
//  Two points search 
        while (left <= right) {
    
            int mid = left + (right - left) / 2;
            if (squareExisted(dp, threshold, mid)) {
    
                left = mid + 1;
            } else {
    
                right = mid - 1;
            }
        }
        return right;
    }


    public static Boolean squareExisted(int[][] sums, int threshold, int len) {
    
        for (int i = 1; i <= m; i++) {
    
            for (int j = 1; j <= n; j++) {
    
                if (i - len < 0 || j - len < 0) {
    
                    continue;
                }
                int tmp = sums[i][j] - sums[i - len][j] - sums[i][j - len] + sums[i - len][j - len];
                if (tmp <= threshold) {
    
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
    
//  Example  1
        int[][] mat = {
    {
    1, 1, 3, 2, 4, 3, 2}, {
    1, 1, 3, 2, 4, 3, 2}, {
    1, 1, 3, 2, 4, 3, 2}};
        int i = maxSideLength(mat, 4);
        System.out.println(i);

//  Example  2
        int[][] mat1 = {
    {
    2, 2, 2, 2, 2, 2, 2}, {
    2, 2, 2, 2, 2, 2, 2}, {
    2, 2, 2, 2, 2, 2, 2}};
        int j = maxSideLength(mat1, 1);
        System.out.println(j);

    }
}

Solution 3 ： A more efficient method

This method makes a direct judgment in the process of establishing the cumulative sum , And each time only judge whether there is a square line longer than the current one 1 The range of , If so, let the result res Self increasing 1, Because the top left vertex can only move one position at a time , Whether to the right , Or move down , The side length can only be increased at most 1. The difficulty of this problem lies in the conversion of subscripts when calculating intervals , Because at this time, the lower right vertex of the square interval is (i, j), The top left vertex is (i-res, j-res), The method of calculating the sum of intervals is sums[i][j] - sums[i - res - 1][j] - sums[i][j - res - 1] + sums[i - res - 1][j - res - 1], The premise is that i - res - 1 and j - res - 1 Are greater than or equal to 0, To prevent cross-border , See code below ：

package com.ice.blindweb;

/* @Auther: sugarice * @Date: 2022/07/24/14:22 * @Description: */

public class main2 {
    


    public static int maxSideLength(int[][] mat, int threshold) {
    
        int m = mat.length;
        int n = mat[0].length;
        int res = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
    
            for (int j = 1; j <= n; j++) {
    
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
                if (i - res - 1 >= 0 && j - res - 1 >= 0 && dp[i][j] - dp[i - res - 1][j] - dp[i][j - res - 1] + dp[i - res - 1][j - res - 1] <= threshold) {
    
                    ++res;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
    
//  Example  1
        int[][] mat = {
    {
    1, 1, 3, 2, 4, 3, 2}, {
    1, 1, 3, 2, 4, 3, 2}, {
    1, 1, 3, 2, 4, 3, 2}};
        int i = maxSideLength(mat, 4);
        System.out.println(i);

//  Example  2
        int[][] mat1 = {
    {
    2, 2, 2, 2, 2, 2, 2}, {
    2, 2, 2, 2, 2, 2, 2}, {
    2, 2, 2, 2, 2, 2, 2}};
        int j = maxSideLength(mat1, 1);
        System.out.println(j);

    }
}