Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Two-dimensional prefix sums make any square's sum available in constant time. Because entries are nonnegative, enlarging a square at the same top-left corner cannot decrease its sum. We also only need to test sizes larger than the best already found, allowing the best size to grow globally throughout the scan.

Approach

Build prefix sums using inclusion-exclusion. At every top-left corner, test the next size beyond the current best, stopping at the matrix boundary. Keep increasing the best while the square sum is at most the threshold; stop this corner after its first failure. In the code, the size argument is a zero-based offset, so it describes a square of side size + 1. Successful tests increase the global answer, and each corner has at most one failed test. Return the final best side length, or zero if no cell qualifies.

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

        for i in range(n):
            for j in range(m):
                ps[i][j] = (
                    mat[i][j]
                    + (ps[i - 1][j] if i > 0 else 0)
                    + (ps[i][j - 1] if j > 0 else 0)
                    - (ps[i - 1][j - 1] if i > 0 and j > 0 else 0)
                )

        def get_sum(i, j, size):
            return (
                ps[i + size][j + size]
                - (ps[i - 1][j + size] if i > 0 and j + size < m else 0)
                - (ps[i + size][j - 1] if i + size < n and j > 0 else 0)
                + (ps[i - 1][j - 1] if i > 0 and j > 0 else 0)
            )

        res = 0
        for i in range(n):
            for j in range(m):
                for k in range(res, min(n - i, m - j)):
                    curr = get_sum(i, j, k)
                    if curr <= threshold:
                        res = k + 1
                    else:
                        break

        return res

Complexity analysis

For an R × C matrix, building the 2-D prefix sums takes O(RC) time and space. During the search, each cell causes at most one failed size check and the global best side length increases at most min(R,C) times, so the displayed scan is also O(RC) time.