Maximum Side Length of a Square with Sum Less than or Equal to Threshold LeetCode solution in Java

1
class Solution {
2
  public int maxSideLength(int[][] mat, int threshold) {
3
    int rows = mat.length;
4
    int cols = mat[0].length;
5
    int[][] preSum = new int[rows + 1][cols + 1];
6
    for (int i = 1; i <= rows; i++) {
7
      for (int j = 1; j <= cols; j++) {
8
        preSum[i][j] =
9
            preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + mat[i - 1][j - 1];
10
      }
11
    }
12
    int lo = 1, hi = Math.min(rows, cols);
13
    while (lo <= hi) {
14
      int m = (lo + hi) >> 1;
15
      if (fun(preSum, threshold, rows, cols, m)) lo = m + 1;
16
      else hi = m - 1;
17
    }
18
    return lo - 1;
19
  }
20

21
  private boolean fun(int[][] preSum, int maxSum, int rows, int cols, int size) {
22
    for (int r = size; r <= rows; r++) {
23
      for (int c = size; c <= cols; c++) {
24
        int sum =
25
            preSum[r][c] - preSum[r - size][c] - preSum[r][c - size] + preSum[r - size][c - size];
26
        if (sum <= maxSum) return true;
27
      }
28
    }
29
    return false;
30
  }
31
}