# Java 8ms/Python 112 ms DP solution. O(mn) time one pass

• 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``````

• Try test case [[0,1,1,0],[0,1,1,0],[0,0,0,0]], I think your code output 1.

• I just tested this. It is 4. And here are some of my tests.

``````['0110', '0110', '0000'] 4
['11', '11'] 4
['01101', '11010', '01110', '11110', '11111', '00000'] 9
['101101', '111111', '011011', '111010', '011111', '110111'] 4
['1111', '1111', '1111'] 9``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.