# Maximal Rectangle

> Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

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

```
0 0 0 0
|--------|
|1 1 1 |1
|1 1 1 |0
|--------|
0 1 0 0
```

```c++
class Solution {
public:
int maximalRectangle(vector > &matrix) {
if(matrix.empty() || matrix[0].empty()) {
return 0;
}

int m = matrix.size();
int n = matrix[0].size();

vector > height(m, vector(n, 0));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == '0') {
height[i][j] = 0;
} else {
height[i][j] = (i == 0) ? 1 : height[i - 1][j] + 1;
}
}
}

int maxArea = 0;
for(int i = 0; i < m; i++) {
maxArea = max(maxArea, largestRectangleArea(height[i]));
}
return maxArea;
}

int largestRectangleArea(vector &height) {
vector s;
height.push_back(0);

int sum = 0;
int i = 0;
while(i < height.size()) {
if(s.empty() || height[i] > height[s.back()]) {
s.push_back(i);
i++;
} else {
int t = s.back();
s.pop_back();
sum = max(sum, height[t] * (s.empty() ? i : i - s.back() - 1));
}
}

return sum;
}
};
```