This page explains Java solution to problem `Maximal Rectangle`

using `Stack`

data structure.

Given a 2D binary matrix filled with `0's`

and `1's`

, find the largest rectangle containing only `1's`

and return its area.

Input:

Input: [

["1","0","1","0","0"],

["1","0","1","1","1"],

["1","1","1","1","1"],

["1","0","0","1","0"]

]Output: 6

```
package com.vc.hard;
import java.util.*;
class MaximalRectangle {
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[] row = new int[n];
int maxLength = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == '1') row[j] += 1;
else row[j] = 0;
}
maxLength = Math.max(maxLength, maxRectangle(row));
}
return maxLength;
}
private int maxRectangle(int[] heights) {
Stack<Integer> st = new Stack<>();
st.push(-1);
int maxLength = 0;
for(int i = 0; i < heights.length; i++) {
while(st.peek() != -1 && heights[st.peek()] > heights[i]) {
maxLength = Math.max(maxLength, heights[st.pop()] * (i - st.peek() - 1));
}
st.push(i);
}
while(st.peek() != -1) {
maxLength = Math.max(maxLength, heights[st.pop()] * (heights.length - st.peek() - 1));
}
return maxLength;
}
}
```

O(M * N) Where

M is total number of Rows in an input array

N is total number of Cols in an input array

O(N) Where

N is total number of Cols in an input array