Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

maxSideLength.js

/**
 * @param {number[][]} mat
 * @param {number} threshold
 * @return {number}
 */
var maxSideLength = function(mat, threshold) {
    const m = mat.length;
    const n = mat[0].length;

    // -----------------------------
    // 1. Build 2D prefix sum matrix
    // -----------------------------
    // pre has size (m+1) x (n+1) to avoid boundary checks.
    const pre = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (let r = 1; r <= m; r++) {
        for (let c = 1; c <= n; c++) {
            pre[r][c] =
                mat[r - 1][c - 1] +
                pre[r - 1][c] +
                pre[r][c - 1] -
                pre[r - 1][c - 1];
        }
    }

    // Helper: compute sum of k×k square with top-left at (r, c)
    function squareSum(r, c, k) {
        const r2 = r + k;
        const c2 = c + k;
        return (
            pre[r2][c2] -
            pre[r][c2] -
            pre[r2][c] +
            pre[r][c]
        );
    }

    // -----------------------------------------
    // 2. Binary search for the maximum side size
    // -----------------------------------------
    let low = 0;
    let high = Math.min(m, n);

    function canFindSquare(k) {
        if (k === 0) return true;
        for (let r = 0; r + k <= m; r++) {
            for (let c = 0; c + k <= n; c++) {
                if (squareSum(r, c, k) <= threshold) {
                    return true;
                }
            }
        }
        return false;
    }

    while (low < high) {
        const mid = Math.floor((low + high + 1) / 2);
        if (canFindSquare(mid)) {
            low = mid; // mid works → try bigger
        } else {
            high = mid - 1; // mid too big → shrink
        }
    }

    return low;
};