**Solution**

**Maximal Square** https://leetcode.com/problems/maximal-square/

**Dynamic Programming**

- Insight for the solution or recurrence comes from comparing the following two examples. In first case, ? is 0. In second case it is 1.

[[1,0]]

[[1,?]]

[[1,1]]

[[1,?]]

```
class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
N, M = len(matrix), len(matrix[0])
table, max_so_far = [[0]*M for _ in range(N)], 0
for i in range(0,N):
for j in range(0,M):
if i == 0:
table[0][j] = int(matrix[0][j])
elif j == 0:
table[i][0] = int(matrix[i][0])
else:
table[i][j] = min(table[i-1][j], table[i][j-1], table[i-1][j-1]) + 1 if int(matrix[i][j]) else 0
max_so_far = max(max_so_far, table[i][j])
return max_so_far*max_so_far
```