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

Array
Binary Search
Matrix
Prefix Sum

TIME

O(m × n × log(min(m, n)))

SPACE

O(m × n)

Intuition

Use 2D prefix sum to compute any submatrix sum in O(1). Binary search on the side length since if a square of size L works, all smaller squares also work (monotonic property).

Solution

Build prefix sum matrix: pref[i][j] = sum of all elements in submatrix from (0,0) to (i-1,j-1).
Binary search on side length: Search for the maximum L where at least one L×L square has sum ≤ threshold.
Check if side L is possible: For each possible top-left corner, compute the L×L square sum using prefix sum formula:
```
sum = pref[i+L][j+L] - pref[i][j+L] - pref[i+L][j] + pref[i][j]
```
Return maximum valid side: The largest L where possible(L) returns true.

Complexity

Time: O(m × n × log(min(m, n))), prefix sum O(mn), binary search O(log(min)) with O(mn) check each
Space: O(m × n), prefix sum matrix

Edge Cases

All elements exceed threshold → return 0
Single cell ≤ threshold → return 1
Entire matrix sum ≤ threshold → return min(m, n)

Code

from typing import List


class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        """
        1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold
        Time: O(m × n × log(min(m, n)))
        Space: O(m × n)
        """
        m, n = len(mat), len(mat[0])

        pref = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                pref[i][j] = (
                    mat[i - 1][j - 1]
                    + pref[i - 1][j]
                    + pref[i][j - 1]
                    - pref[i - 1][j - 1]
                )

        def possible(L: int) -> bool:
            for i in range(m - L + 1):
                for j in range(n - L + 1):
                    total = (
                        pref[i + L][j + L]
                        - pref[i][j + L]
                        - pref[i + L][j]
                        + pref[i][j]
                    )
                    if total <= threshold:
                        return True
            return False

        low, high = 0, min(m, n)
        ans = 0

        while low <= high:
            mid = (low + high) // 2
            if possible(mid):
                ans = mid
                low = mid + 1
            else:
                high = mid - 1

        return ans

/**
 * 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold
 * Time: O(m × n × log(min(m, n)))
 * Space: O(m × n)
 */
class Solution {
    private int[][] pref;
    private int m, n, threshold;

    public int maxSideLength(int[][] mat, int threshold) {
        this.m = mat.length;
        this.n = mat[0].length;
        this.threshold = threshold;

        pref = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                pref[i][j] = mat[i - 1][j - 1]
                           + pref[i - 1][j]
                           + pref[i][j - 1]
                           - pref[i - 1][j - 1];
            }
        }

        int low = 0, high = Math.min(m, n);
        int ans = 0;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (possible(mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return ans;
    }

    private boolean possible(int L) {
        for (int i = 0; i <= m - L; i++) {
            for (int j = 0; j <= n - L; j++) {
                int total = pref[i + L][j + L]
                          - pref[i][j + L]
                          - pref[i + L][j]
                          + pref[i][j];
                if (total <= threshold) {
                    return true;
                }
            }
        }
        return false;
    }
}