# Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

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

Return 4.

Tips:

DP, O(mn) Space, O(mn) time

Top, Left, and top Left decides the size of the square. If all of them are same, then the size of square increases by 1. If they're not same, they can increase by 1 to the minimal square.

Code：

``````public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int[][] result = new int[m][n];
int max = 0;
//initialize
for (int i = 0; i < m; i++) {
result[i][0] = matrix[i][0] == '1' ? 1 : 0;
max = Math.max(max, result[i][0]);
}
for (int i = 0; i < n; i++) {
result[0][i] = matrix[0][i] == '1' ? 1 : 0;
max = Math.max(max, result[0][i]);
}
//dp: top, Left, and Top Left decides the size of the square. If all of them are same, then the size of square increases by 1. If they're not same, they can increase by 1 to the minimal square.
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == '1') {
result[i][j] = Math.min(result[i - 1][j], Math.min(result[i][j - 1], result[i - 1][j - 1])) + 1;
}
max = Math.max(max, result[i][j]);
}
}
return max * max;
}
}
``````

``````public int maximalSquare(char[][] matrix){
if (matrix == null || matrix.length == 0) {
return 0;
}
int max = 0;
int m = matrix.length;
int n = matrix[0].length;
int [][]result = new int [2][n];
for(int i = 0; i < m; i++){
result[i % 2][0] = matrix[i][0] == '1' ? 1 : 0;
max = Math.max(result[i%2][0] , max);
for(int j = 1; j < n; j++) {
if(i > 0) {
if(matrix[i][j] =='1') {
result[i%2][j] = Math.min(result[(i - 1)%2][j],Math.min(result[i%2][j-1], result[(i-1)%2][j-1])) + 1;
} else {
result[i%2][j] = 0;
}
}
else {
result[0][j] = matrix[0][j] == '1' ? 1 : 0;
}
max = Math.max(result[i%2][j], max);
}
}
return max * max;
}
``````