## Maximum area rectangle in a binary matrix

In this problem, we are given a binary matrix and we are required to find the largest area of rectangle.I have explained the intuition for solving this problem by giving some examples and then I have shown diagramatically, how to solve this problem by using the same concept of dp as we used to solve the problem of finding the largest rectangle area in a histogram.I have given dry run idea and at the end of the video, I have also shown the code walkthrough.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below.

```class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n),right(n);

stack<int> mystack;
for(int i=0;i<n;++i)    //Fill left
{
if(mystack.empty())
{    left[i] = 0;   mystack.push(i);    }
else
{
while(!mystack.empty() and heights[mystack.top()]>=heights[i])
mystack.pop();
left[i] = mystack.empty()?0:mystack.top()+1;
mystack.push(i);
}
}
while(!mystack.empty()) //Clear stack
mystack.pop();

for(int i=n-1;i>=0;--i) //Fill right
{
if(mystack.empty())
{   right[i] = n-1; mystack.push(i);    }
else
{
while(!mystack.empty() and heights[mystack.top()]>=heights[i])
mystack.pop();
right[i] = mystack.empty()?n-1:mystack.top()-1;
mystack.push(i);
}
}
int mx_area = 0;    //Stores max_area
for(int i=0;i<n;++i)
mx_area = max(mx_area,heights[i]*(right[i]-left[i]+1));
return mx_area;
}
};```

### One comment on “Maximum area rectangle in a binary matrix”

• Tech Dose July 3, 2021