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

Problem statement

<font color = https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/

Solution

For given size mid of square check if we have good matrix, using 2d-cumulative sums. Then use binary search.

Complexity

It is O(nm*log(min(m, n))) for time and O(mn) for space.

Code

class Solution:
    def maxSideLength(self, M, t):
        m, n = len(M), len(M[0])
        dp = [[0] * (n+1) for _ in range(m+1)] 
        for c, r in product(range(n), range(m)):
            dp[r+1][c+1] = dp[r+1][c] + dp[r][c+1] - dp[r][c] + M[r][c]
            
        beg, end = -1, min(m, n) + 1
        while beg + 1 < end:
            mid = (beg + end)//2
            Found = False
            for r in range(m - mid):
                for c in range(n - mid):
                    if dp[r+mid+1][c+mid+1] - dp[r][c+mid+1] - dp[r+mid+1][c] + dp[r][c] <= t:
                        Found = True
            if Found:
                beg = mid
            else:
                end = mid
                
        return end