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

1
/**
2
 * @param {number[][]} mat
3
 * @param {number} threshold
4
 * @return {number}
5
 */
6
var maxSideLength = function (mat, threshold) {
7
  const n = mat.length,
8
    m = mat[0].length;
9

10
  // build sum matrix
11
  let sum = [];
12
  for (let i = 0; i <= n; i++) {
13
    sum.push(new Array(m + 1).fill(0));
14
    for (let j = 0; j <= m; j++) {
15
      if (i == 0 || j == 0) {
16
        continue;
17
      }
18
      sum[i][j] =
19
        sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
20
    }
21
  }
22

23
  // function to check square sum <= threshold
24
  const underThreshold = function (len) {
25
    for (let i = len; i <= n; i++) {
26
      for (let j = len; j <= m; j++) {
27
        if (
28
          sum[i][j] -
29
            sum[i - len][j] -
30
            sum[i][j - len] +
31
            sum[i - len][j - len] <=
32
          threshold
33
        ) {
34
          return true;
35
        }
36
      }
37
    }
38
    return false;
39
  };
40

41
  // binary search
42
  let l = 0,
43
    r = Math.min(n, m);
44
  while (l <= r) {
45
    const mid = Math.floor((l + r) / 2);
46
    if (underThreshold(mid)) {
47
      l = mid + 1;
48
    } else {
49
      r = mid - 1;
50
    }
51
  }
52
  return r;
53
};