# [leetcode] Maximal Rectangle

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.

tags: array, stack, hash table, dynamic programming

```class Solution {
public:
/**
* assume the size of 2D array is n*m.
* this is a brute violent algorithm with the O((nm)^2) time complexity.
* **/

int maximalRectangle(vector<vector<char> > &matrix) {
//handle empty input
if(matrix.empty()){
return 0;
}

int maxArea = 0;
int height = matrix.size();
int length = matrix[0].size();

//(sx, sy) is the left-top corner of a possible rectangle
for(int sy = 0; sy < height; sy++){
for(int sx = 0; sx < length; sx++){
if(matrix[sy][sx] == '1'){

//(x,y) is the right-bottom corner of a possible rectangle
int maxLength = length;
for(int y = sy; y < height; y++){
for(int x = sx; x < length; x++){
if(matrix[y][x] == '0' || x - sx + 1 == maxLength){

//update maxLength
maxLength = x - sx + 1;
int thisArea = (x - sx + 1) * (y - sy + 1);
maxArea = max(maxArea, thisArea);
}
}
}
}
}
}

return maxArea;
}
};```

```1010        1010
1011    =>  2021
1011    =>  3032
1111        4143```

http://blog.csdn.net/havenoidea/article/details/11854723

```class Solution {
public:
/**
* O(nm)
**/
int maximalRectangle(vector<vector<char> > &matrix) {

if(matrix.empty()){
return 0;
}

int height = matrix.size();
int length = matrix[0].size();
int maxArea = 0;
//s stores possible left-bottom start corner.
stack<int> s;

//map stores the current rectangle height of current column.
int map[height][length];

for(int i = 0; i < length; i++){
map[0][i] = matrix[0][i] == '1'?1:0;
}

for(int j = 1; j < height; j++){
for(int i = 0; i < length; i++){
map[j][i] = matrix[j][i] == '1'?map[j - 1][i] + 1:0;
}
}

for(int i = 0; i < height; i++){
int j = 0;
while(j != length){
if(s.empty()){
s.push(j);
j++;
}

//s is not empty
else{
if (map[i][j] >= map[i][s.top()]){
s.push(j);
j++;
}
//map[i][j] < the top of stack
else{
while(map[i][j] < map[i][s.top()]){
int t = s.top();
s.pop();
int start = s.empty()?-1:s.top();
int thisArea = map[i][t] * (j - start - 1);
maxArea = max(thisArea, maxArea);
if (s.empty()){
break;
}
}
//push j into the stack, now map[i][j] >= the top of stack

}
}
}
// j == length , at the end of the row
while(!s.empty()){
int t = s.top();
s.pop();
int start = s.empty()?-1:s.top();
int thisArea = map[i][t] * (length - start - 1);
maxArea = max(thisArea, maxArea);
}
}
return maxArea;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.