class Solution:
    '''
    Time Complexity: O(m * n * log(min(m, n)))
    Space Complexity: O(m * n)
    Where, m is number of rows, n is number of columns in the matrix.
    Prefix sums + Binary Search problem.
    DID NOT GO THROUGH THE SOLUTION YET!
    '''
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        m, n = len(mat), len(mat[0])

        # Build prefix sum array
        pre = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                pre[i][j] = (
                    mat[i - 1][j - 1]
                    + pre[i - 1][j]
                    + pre[i][j - 1]
                    - pre[i - 1][j - 1]
                )

        # Check if there exists a square of side k with sum <= threshold
        def can(k):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    total = (
                        pre[i + k][j + k]
                        - pre[i][j + k]
                        - pre[i + k][j]
                        + pre[i][j]
                    )
                    if total <= threshold:
                        return True
            return False

        # Binary search on side length
        low, high = 0, min(m, n)
        ans = 0
        while low <= high:
            mid = (low + high) // 2
            if can(mid):
                ans = mid
                low = mid + 1
            else:
                high = mid - 1

        return ans