Maximum Side Length of a Square with Sum Less than or Equal to Threshold

• Preprocessing: Prefix Sums
  1. Create a 2D prefix sum array, prefix, of size (m+1) x (n+1) to store cumulative sums.
  2. Iterate through the input matrix mat to populate the prefix array. The sum of the rectangle from (0,0) to (i-1,j-1) is calculated as: prefix[i][j] = mat[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1].
• Main Logic: Iteration
  1. Iterate through all possible side lengths k in descending order, from min(m, n) down to 1.
  2. For each k, iterate through all possible top-left corners (r, c) of a k x k square.
  3. Calculate the sum of the current square in O(1) time using the prefix array: sum = prefix[r+k][c+k] - prefix[r][c+k] - prefix[r+k][c] + prefix[r][c].
  4. If sum <= threshold, we have found a valid square. Since we are iterating k from largest to smallest, this k must be the maximum possible side length. Return k immediately.
  5. If the loops complete without finding any valid square, it means no such square exists. Return 0.

The core of this method is the optimization of the sum calculation. Instead of summing up k*k elements for every square, we pre-process the matrix in O(m*n) time to build a prefix sum array. prefix[i+1][j+1] stores the sum of all elements in the rectangle from mat[0][0] to mat[i][j].

With the prefix array, the sum of a square with top-left corner (r, c) and side length k can be found in O(1) using an inclusion-exclusion principle. The algorithm then searches for the answer by checking side lengths in a linear scan, from min(m, n) down to 1. The first side length k for which a valid square is found is guaranteed to be the maximum, so we can return it immediately. If the scan completes, no valid square exists, and we return 0.

1class Solution {2    public int maxSideLength(int[][] mat, int threshold) {3        int m = mat.length;4        int n = mat[0].length;5        int[][] prefix = new int[m + 1][n + 1];6        for (int i = 1; i <= m; i++) {7            for (int j = 1; j <= n; j++) {8                prefix[i][j] = mat[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];9            }10        }11 12        for (int k = Math.min(m, n); k >= 1; k--) {13            for (int r = 0; r <= m - k; r++) {14                for (int c = 0; c <= n - k; c++) {15                    // In the prefix sum array, the indices are 1-based.16                    // A square from (r, c) to (r+k-1, c+k-1) in mat corresponds to17                    // the rectangle between (r, c) and (r+k, c+k) in the prefix sum grid.18                    int sum = prefix[r + k][c + k] - prefix[r][c + k] - prefix[r + k][c] + prefix[r][c];19                    if (sum <= threshold) {20                        return k; // Found the largest possible k21                    }22                }23            }24        }25        26        return 0; // No square found27    }28}

• Preprocessing: Prefix Sums
  1. As in the previous approach, create and populate a (m+1) x (n+1) 2D prefix sum array in O(m*n) time.
• Helper Function: hasValidSquare(k)
  1. Create a function that takes a side length k and checks if any k x k square has a sum less than or equal to threshold.
  2. This function iterates through all possible k x k squares, calculates their sum in O(1) using the prefix sum array, and returns true if a valid one is found. Otherwise, it returns false after checking all possibilities. This check takes O(m*n) time.
• Binary Search
  1. Initialize search boundaries low = 0, high = min(m, n), and a result variable ans = 0.
  2. While low <= high: a. Calculate the middle side length mid = low + (high - low) / 2. b. Call hasValidSquare(mid). c. If it returns true, mid is a possible answer. We try for a larger square by setting ans = mid and low = mid + 1. d. If it returns false, mid is too large. We search in the lower half by setting high = mid - 1.
  3. Return ans.

The foundation of this method is to transform the problem from finding a maximum value to a series of decision problems. Instead of asking "What is the max length?", we ask "Does a square of length k exist?". This yes/no question can be answered efficiently.

First, we pre-compute the 2D prefix sum array in O(m*n) time, which allows for O(1) sum queries for any submatrix.

Then, we perform a binary search on the possible side lengths k. For each mid value in our binary search, we have a helper function, hasValidSquare(mid), which determines if there's any square of size mid x mid with a sum <= threshold. This check takes O(m*n) time.

If hasValidSquare(mid) is true, we know mid is a potential answer, and we try to find an even larger one by searching in the upper half (low = mid + 1). If it's false, mid is too large, and we must search for a smaller side length in the lower half (high = mid - 1). The largest mid for which the check was successful is stored and eventually returned as the answer.

1class Solution {2    public int maxSideLength(int[][] mat, int threshold) {3        int m = mat.length;4        int n = mat[0].length;5        int[][] prefix = new int[m + 1][n + 1];6        for (int i = 1; i <= m; i++) {7            for (int j = 1; j <= n; j++) {8                prefix[i][j] = mat[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];9            }10        }11 12        int low = 0, high = Math.min(m, n), ans = 0;13        while (low <= high) {14            int mid = low + (high - low) / 2;15            if (mid == 0) {16                low = mid + 1;17                continue;18            }19            if (hasValidSquare(mid, m, n, prefix, threshold)) {20                ans = mid; // mid is a possible answer, try for a larger one21                low = mid + 1;22            } else {23                high = mid - 1; // mid is too large, try a smaller one24            }25        }26        return ans;27    }28 29    private boolean hasValidSquare(int k, int m, int n, int[][] prefix, int threshold) {30        for (int r = 0; r <= m - k; r++) {31            for (int c = 0; c <= n - k; c++) {32                int sum = prefix[r + k][c + k] - prefix[r][c + k] - prefix[r + k][c] + prefix[r][c];33                if (sum <= threshold) {34                    return true;35                }36            }37        }38        return false;39    }40}