My logic is a bit different than others. Still dynamic programming. `a`

is the side length of current maximum square found. `dp[i][j+1]`

is the side length of maximum square with `matrix[i][j]`

as the lower right corner. `dp`

is reduced from a matrix to a vector since new values of `dp[i][j+1]`

only depend on it's up and left neighbor. `k`

is the minimum side length of the two neighbor squares.

```
(1) dp[i][j+1] = 0 if matrix[i][j] == '0'
(2) dp[i][j+1] = k+1 if matrix[i][j] == '1' and matrix[i-k][j-k] =='1'
(3) dp[i][j+1] = k otherwise
```

**Java**

```
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0)
return 0;
int m = matrix.length, n = matrix[0].length;
int[] dp = new int[n + 1];
int a = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '0')
dp[j + 1] = 0;
else {
int k = Math.min(dp[j], dp[j + 1]);
if (matrix[i - k][j - k] == '1') ++k;
dp[j + 1] = k;
a = Math.max(a, k);
}
}
return a * a;
}
//Runtime: 8 ms
```

**Python**

```
def maximalSquare(self, matrix):
if not matrix:
return 0
a, m, n = 0, len(matrix), len(matrix[0])
dp = [0] * (n + 1)
for i in xrange(m):
for j in xrange(n):
if matrix[i][j] == '0':
dp[j + 1] = 0
else:
k = min(dp[j], dp[j + 1])
if matrix[i - k][j - k] == '1':
k += 1
a = max(a, k)
dp[j + 1] = k
return a * a
# Runtime: 112 ms
```