221. Maximal Square

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

Python

Bottom Up DP

• Time: O(M*N)
• Space: O(M*N)

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])

        dp = [[0]*(n+1) for _ in range(m+1)]
        ans = 0

        for row in range(1, m+1):
            for col in range(1, n+1):
                if matrix[row-1][col-1] != "1":
                    continue

                dp[row][col] = 1 + min([
                    dp[row-1][col], dp[row][col-1], dp[row-1][col-1]
                ])

                ans = max(ans, dp[row][col])

        return ans**2