Problem statement

https://leetcode.com/problems/maximal-square/

Solution

Classical DP problem, where by dp[i][j] we define the biggest square whose bottom right corner is the cell with index (i,j) in the original matrix. Then we can use dp(i, j)= min(dp(i-1, j), dp(i-1, j-1), dp(i, j-1)) + 1 to update cells, if we have 1 in (i, j) place in original matrix.

Complexity

Time complexity is O(mn) and the same space. Space complexity can be reduced to O(min(m, n)), because we use only one row at a time.

Code

class Solution:
    def maximalSquare(self, M):
        m, n = len(M[0]), len(M)
        @lru_cache(None)
        def dp(i, j):
            if M[i][j] == "0": return 0
            if i < 0 or j < 0: return 0
            return min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1)) + 1
        
        return max(dp(i, j) for i, j in product(range(n), range(m)))**2