# Leetcode 221. Maximal Square

## 題解

### Brute force (TLE)

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # Time complexity: O(mn * min(m,n))
        # Space complexity: O(1)
        m,n = len(matrix), len(matrix[0])
        maxSide = 0
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == "1":
                    maxSide = max(maxSide, 1)
                    currentMaxSide = min(m - y, n - x)
                    for k in range(1, currentMaxSide):
                        flag = True
                        if matrix[y + k][x + k] == '0':
                            break
                        for b in range(k):
                            if matrix[y + k][x + b] == '0' or matrix[y + b][x + k] == '0':
                                flag = False
                                break
                        if flag:
                            maxSide = max(maxSide, k + 1)
                        else:
                            break
        return maxSide ** 2

### DP

#### 狀態轉移公式


dp[_y][_x] = min(
    dp[_y-1][_x-1], # 左上
    dp[_y-1][_x], # 上
    dp[_y][_x-1] # 左
) + 1 if matrix[y][x] == "1" else 0

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # Time complexity: O(mn)
        # Space complexity: O((m+1)*(n+1))
        # dp[y][x] = min(dp[y-1][x-1],dp[y-1][x],dp[y][x-1]) + 1 if matrix[y][x] == "1" else 0
        m,n = len(matrix),len(matrix[0])
        output = 0
        dp = [([0] * (n + 1)) for i in range(m+1)]
        for i in range(m*n):
            y,x = i // n, i % n
            _y,_x = y+1,x+1
            dp[_y][_x] = min(
                dp[_y-1][_x-1],
                dp[_y-1][_x],
                dp[_y][_x-1]
            ) + 1 if matrix[y][x] == "1" else 0
            output = max(output,dp[_y][_x])
        return output ** 2

### 狀態壓縮

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # Time complexity: O(mn)
        # Space complexity: O((n+1)^2)
        m,n = len(matrix),len(matrix[0])
        output = 0
        dp = [0 for i in range(n+1)]
        new_dp = [0 for i in range(n+1)]
        for y in range(m):
            prev = 0
            for x in range(n):
                _x = x+1
                new_dp[_x] = min(
                    dp[_x-1], # top left
                    dp[_x], # top
                    prev, # left
                ) + 1 if matrix[y][x] == "1" else 0
                output = max(output,new_dp[_x])
                prev = new_dp[_x]
            dp = new_dp[:]
        return output ** 2

##### Space O(n+1)

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # Time complexity: O(mn)
        # Space complexity: O(n+1)
        m,n = len(matrix),len(matrix[0])
        output = 0
        dp = [0 for i in range(n+1)]
        for y in range(m):
            top_left = 0
            for x in range(n):
                _x = x+1
                original_top_left = top_left
                top_left = dp[_x]
                dp[_x] = min(
                    original_top_left, # top left
                    dp[_x], # top
                    dp[_x-1], # left
                ) + 1 if matrix[y][x] == "1" else 0
                output = max(output,dp[_x])
        return output ** 2