# Share my Java solution with time O(n^2), space O(n)

• Beats 48.19% of java submissions.

``````// Time : O(n^2) Space : O(n)
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length ==0) return 0;
int[] hist = new int[matrix[0].length];
for (int i = 0 ; i < matrix[0].length ; i++) {
hist[i] = matrix[0][i] == '1' ? 1 : 0;
}
int max = maxHist(hist);
for (int i = 1 ; i < matrix.length ; i++) {
for (int j = 0 ; j < matrix[0].length ; j++) {
if (matrix[i][j] == '0') {
hist[j] = 0;
} else {
hist[j] = hist[j] + 1;
}
}
max = Math.max(max, maxHist(hist));
}

return max;
}

private int maxHist(int[] hist) {
Stack<Integer> stack = new Stack<>();
int n = hist.length;
int i = 0;
int max = 0;
while(i < n) {
while (!stack.isEmpty() && hist[i] < hist[stack.peek()]) {
max = Math.max(max, hist[stack.pop()] * (i - (stack.isEmpty() ? 0 : stack.peek() + 1)));
}
stack.push(i++);
}

while(stack.isEmpty() == false) {
max = Math.max(max, hist[stack.pop()] * (n - (stack.isEmpty() ? 0 : stack.peek() + 1)));
}
return max;
}``````

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