find largest rectangle with value 1 return its area
int maxRectangle(vector<char> arr)
{
stack<int> ss ;
int maxArea = 0, i = 0; //logic to handle 0110
while (i < arr.size()) {
if (ss.empty() || (arr[i] – ‘0’) >= (arr[ss.top()] – ‘0’)) {
ss.push(i++);
} else {
int top=ss.top();
ss.pop();
int diff=arr[top]-‘0’;
maxArea = max(maxArea, (arr[top]-‘0’)*(ss.empty() ? i : (i – (ss.top()) – 1)));
// i++;
}
}
while (!ss.empty()) { // in case number end with 1 or elements till u find 0
char top=ss.top();
ss.pop();
int diff = arr[top] – ‘0’; // gives
int diff1=ss.empty() ? i : (i – ss.top() – 1);
maxArea = max(maxArea,(diff)*(ss.empty() ? i : (i – ss.top() – 1)));
}
return maxArea;
}
//Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.
int maximalRectangle(vector<vector<char> > &matrix) {
int rows = matrix.size();
if (rows == 0) return 0;
int numCol = matrix[0].size();
if(rows==1 && numCol==1)
return (matrix[0][0] -‘0’);
vector<vector<char> > matrix1;
vector< vector<char> >::iterator row;
vector<char>::iterator col;
matrix1=matrix;
if(rows >1)
{
for (row = matrix1.begin()+1; row != matrix1.end(); row++) {
for (col = row->begin(); col != row->end(); col++) {
if((*col-‘0’)!=0)
{
*col=1+(*((row-1)->begin()+(col – row->begin()))-‘0’) + ‘0’;
}
}
}
}
int maxArea = 0;
for (int i=0; i<rows; ++i) {
maxArea =max(maxArea, maxRectangle(matrix1[i]));
}
return maxArea;
}