MAXIMAL-RECTANGLE leetcode Solution - Correct, Optimal and Working

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

int result = INT_MIN;
int row = matrix.size();

if( row == 0 ) {
return 0;
}

int col = matrix[0].size();

/*if( row == 1 && col == 1 ) {
return matrix[0][0] - '0';
}*/

int array[row][col];

for( int i = 0 ; i < row ; i++ ) {
for( int j = 0 ; j < col; j++ ) {
if( i == 0 ) {
array[i][j] = matrix[i][j] - '0';
}
else {
if( matrix[i][j] == '0' ) {
array[i][j] = 0;
}
else {
// matrix[i][j] has to be 1
array[i][j] = array[i-1][j] + (matrix[i][j] - '0');
}
}
}

stack<int> s;
int k = 0;
int m = INT_MIN;
while( k < col ) {
if( s.empty() || array[i][k] > array[i][s.top()] ) {
s.push(k);
k++;
}
else {
int tp = s.top();
s.pop();

int h = array[i][tp];
int w = (s.empty()) ? k : (k - s.top() - 1);
int area = h * w;
m = max(m,area);
}
}

while( s.empty() == false ) {
int tp = s.top();
s.pop();
int h = array[i][tp];
int w = (s.empty()) ? k : (k - s.top() - 1);
int area = h * w;
m = max(m,area);
}

result = max(result,m);

}
return result;
}
};
``````