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

/**
 * Problem: LeetCode 1292 - Maximum Side Length of a Square with Sum Less than or Equal to Threshold
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] pref = new int[m + 1][n + 1];

        // Precompute 2D prefix sums
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pref[i + 1][j + 1] = mat[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j];
            }
        }

        int maxLen = 0;

        // Greedily expand side length at each candidate bottom-right corner (i, j)
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i > maxLen && j > maxLen) {
                    int k = maxLen + 1;
                    int sum = pref[i][j] - pref[i - k][j] - pref[i][j - k] + pref[i - k][j - k];
                    if (sum <= threshold) {
                        maxLen++;
                    }
                }
            }
        }

        return maxLen;
    }
}

"""
Problem: LeetCode 1292 - Maximum Side Length of a Square with Sum Less than or Equal to Threshold
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        m, n = len(mat), len(mat[0])
        pref = [[0] * (n + 1) for _ in range(m + 1)]

        # Precompute 2D prefix sum table
        for i in range(m):
            for j in range(n):
                pref[i + 1][j + 1] = mat[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j]

        max_len = 0

        # Greedily attempt to increase side length at each bottom-right corner (i, j)
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if i > max_len and j > max_len:
                    k = max_len + 1
                    sub_sum = pref[i][j] - pref[i - k][j] - pref[i][j - k] + pref[i - k][j - k]
                    if sub_sum <= threshold:
                        max_len += 1

        return max_len

/**
 * Problem: LeetCode 1292 - Maximum Side Length of a Square with Sum Less than or Equal to Threshold
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> pref(m + 1, vector<int>(n + 1, 0));

        // Precompute 2D prefix sums
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pref[i + 1][j + 1] = mat[i][j] + pref[i + 1][j] + pref[i][j + 1] - pref[i][j];
            }
        }

        int maxLen = 0;

        // Greedily expand side length at each candidate bottom-right corner
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i > maxLen && j > maxLen) {
                    int k = maxLen + 1;
                    int sum = pref[i][j] - pref[i - k][j] - pref[i][j - k] + pref[i - k][j - k];
                    if (sum <= threshold) {
                        maxLen++;
                    }
                }
            }
        }

        return maxLen;
    }
};

/**
 * Problem: LeetCode 1292 - Maximum Side Length of a Square with Sum Less than or Equal to Threshold
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[][]} mat
 * @param {number} threshold
 * @return {number}
 */
var maxSideLength = function(mat, threshold) {
    const m = mat.length;
    const n = mat[0].length;
    const pref = Array.from({ length: m + 1 }, () => new Int32Array(n + 1));

    // Precompute 2D prefix sums
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            pref[i + 1][j + 1] = mat[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j];
        }
    }

    let maxLen = 0;

    // Greedily test if a square of side (maxLen + 1) ending at (i, j) fits threshold
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (i > maxLen && j > maxLen) {
                const k = maxLen + 1;
                const sum = pref[i][j] - pref[i - k][j] - pref[i][j - k] + pref[i - k][j - k];
                if (sum <= threshold) {
                    maxLen++;
                }
            }
        }
    }

    return maxLen;
};