# Java Solution Beat 86%, 11ms

• The idea is come from "Largest Rectangle in Histogram" question, I use one height array to record the height, the trick part is how to calculate the square. The most important condition is right - left must be less than height[right], this is because if the right - left > height[right], the max area will not exist in that area.

``````private int getSquareArea(int[] height){
int maxArea = 0;
for (int left = 0; left < height.length; left++){
int right = left, minHeight = height[left];
while (right < height.length && height[right] != 0 && right - left <= height[right]){
minHeight = Math.min(minHeight, height[right++]);
}
int width = right - left;
int edge = Math.min(minHeight, width);
maxArea = Math.max(edge * edge, maxArea);
}
return maxArea;
}

public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0){
return 0;
}
int[] height = new int[matrix[0].length];
int maxArea = 0;
for (int rowIndex = 0; rowIndex < matrix.length; rowIndex++){
for (int colIndex = 0; colIndex < matrix[0].length; colIndex++){
if (matrix[rowIndex][colIndex] == '0'){
height[colIndex] = 0;
}else{
height[colIndex] += 1;
}
}
maxArea = Math.max(maxArea, getSquareArea(height));
}
return maxArea;
}``````

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