---
# System prepended metadata

title: Leetcode 221.

---

# Leetcode 221. Maximal Square

## 題解

### Brute force (TLE)

```python!
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

#### 狀態轉移公式

![](https://hackmd.io/_uploads/ByuXt17e6.png)

```python!
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
```

```python!
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
```

### 狀態壓縮

```python!
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)

```python!
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
```

![](https://hackmd.io/_uploads/HJxa_4mga.png)