# Ac solution code

• Example:

``````1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 1 1 1

1 0 1 0 0
1 0 1 1 1
1 1 1 a b
1 0 1 c d
``````

The above 2 matrixes are the same, I just want to mark the nodes: a, b, c, d. (Char of these 4 nodes are all '1').

maxEdge[i][j]: max square edge length with right-bottom vertex (i-1, j-1)(i=1..n, j=1..m)

The max square edge length with right-bottom vertex d is determined by vertex a, b, c:

``````Vertical edge vMax(d) is determined by: min(maxEdge(a), maxEdge(b))
Horizon  edge hMax(d) is determined by: min(maxEdge(a), maxEdge(c))

maxEdge of square(d)
= min(vMax(d), hMax(d))
= min(maxEdge(a), maxEdge(b), maxEdge(a), maxEdge(c))
= min(maxEdge(a), maxEdge(b), maxEdge(c))
``````

JAVA Code: Runtime = O(nm); Space = O(nm)

``````public int maximalSquare(char[][] A) {
if (A == null || A.length == 0) return 0;
int n = A.length, m = A[0].length, max = 0;
int maxEdge[][] = new int[n + 1][m + 1];// maxEdge[i][j]: max square edge length with right-bottom vertex (i-1, j-1)(i=1..n, j=1..m)
for (int i = 1; i <=n; i++) {
for (int j = 1; j <= m; j++) {
if (A[i-1][j-1] == '1') {//  Choose the minimum square with right-bottom vertex (i-1, j-1)
maxEdge[i][j] = Math.min(maxEdge[i-1][j], Math.min(maxEdge[i][j-1], maxEdge[i-1][j-1])) + 1;
max = Math.max(max, maxEdge[i][j]);
}
}
}
return max * max;
}``````

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