Daily LeetCode - by Vítor Belim

Description

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.

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
Explanation: The maximum side length of square with sum less than or equal to 4 is 2 as shown.

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

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 300
0 <= mat[i][j] <= 10⁴
0 <= threshold <= 10⁵

Solutions

This function finds the largest square you can fit in a 2D matrix where the sum of all elements inside doesn't exceed a threshold. It works by first building a prefix sum array (dp) that lets it calculate the sum of any rectangular region in constant time using the formula sum(rect) = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]. Then it systematically checks every possible position in the matrix, and at each position it tests increasingly larger squares (incrementing the side length) until it finds one that exceeds the threshold. Since it tracks the best result found so far, it returns the maximum side length of any square that stays within the threshold limit.

Language: javascript(2026-01-19 09:14)DONE

CPU Performance75.00%

Memory Performance75.00%

/**
 * @param {number[][]} mat
 * @param {number} threshold
 * @return {number}
 */
var maxSideLength = function (mat, threshold) {
    const m = mat.length;
    const n = mat[0].length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
        }
    }

    const getRect = (x1, y1, x2, y2) => {
        return dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
    };

    const r = Math.min(m, n);
    let res = 0;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            for (let c = res + 1; c <= r; c++) {
                if (i + c - 1 <= m &&
                    j + c - 1 <= n &&
                    getRect(i, j, i + c - 1, j + c - 1) <= threshold) {
                    res = c;
                } else {
                    break;
                }
            }
        }
    }

    return res;
};

Description

Solutions

AI Explanation