# Simplest and fastest solution. O(N^2) runtime, O(N) space

• ``````/**
* Same algorithm as the "max rectangle in histogram" problem.
* Keep track of the "column run" for each column and apply that algorithm
* to each row. Column run is the number of contiguous 1's.
*/

struct run{
int index, value;
run(int index_, int value_): index(index_), value(value_){}
};
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
if(!matrix.size())return 0;
const int nRows = matrix.size(), nCols = matrix[0].size();
vector<run> seqs;
vector<int> colRuns(nCols,0);
int i,j,ans=0;
for(i=0;i<nRows;i++){
seqs.assign(1,run(0,-1)); // sentinel value
for(j=0;j<nCols;j++){
int ch=matrix[i][j]-'0';
int cur = colRuns[j] = (colRuns[j] & -ch)+ch; // increment by 1 if ch is 1, else set to 0.
int idx=j;
while(seqs.back().value>=cur){
run& r = seqs.back();
ans=max(ans,r.value*(j-r.index));
idx=r.index;
seqs.pop_back();
}
seqs.push_back(run(idx,cur));
}
while(seqs.size()>1){
run& r = seqs.back();
ans=max(ans,r.value*(nCols-r.index));
seqs.pop_back();
}
}
return ans;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.