# Evolve from brute force to optimal

• This problem is similar to maximal square but much more difficult.

1. brute force O(n^6), count each rectangle
``````    int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.empty()) return 0;
int r = matrix.size(), c = matrix[0].size(), area = 0;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++) { //each start point (i,j)
if(matrix[i][j]=='0') continue;
for(int p=i;p<r;p++)
for(int q=j;q<c;q++) { // each end point (p,q)
if(matrix[p][q]=='0') continue;
bool ones = 1;
for(int x=i;x<=p;x++) {   //check if the rectangle contains all 1s
for(int y=j;y<=q;y++)
if(matrix[x][y] == '0') {
ones = 0;
break;
}
if(!ones) break;
}
if(ones) area = max(area, (p-i+1)*(q-j+1));
}
}
return area;
}
``````
1. O(n^4), whether a rectangle contains all 1s can be determined incrementally from the previous rectangle
``````    int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.empty()) return 0;
int r = matrix.size(), c = matrix[0].size(), area = 0;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++) {
vector<vector<bool>> dp(r,vector<bool>(c));
for(int p=i;p<r;p++)
for(int q=j;q<c;q++) {
dp[p][q] = matrix[p][q]=='1';
if(p>i) dp[p][q] = dp[p][q] & dp[p-1][q];
if(q>j) dp[p][q] = dp[p][q] & dp[p][q-1];
if(dp[p][q]) area=max(area,(p-i+1)*(q-j+1));
else break;
}
}
return area;
}
``````
1. O(n^3), for a start/end point, we do not need to consider all end/start points, we only need to consider points that connect to the start/end point by all 1s. We use a 2d array to cache number of consecutive 1s to the left of each point. Then for a point, we can determine its maximal rectangles in linear time. The idea is from @uniqueness .
``````    int maximalRectangle(vector<vector<char>>& matrix) {
int r = matrix.size();
if (!r) return 0;
int c = matrix[0].size(), area = 0;
vector<vector<int>> ones(r,vector<int>(c));
for(int i=0;i<r;i++)
for(int j=0;j<c;j++) {
if(matrix[i][j]=='0') continue;
int w = ones[i][j] = (j?ones[i][j-1]:0) + 1;
for(int k=i; k>=0; k--) {
w = min(ones[k][j],w);
area = max(area,w*(i-k+1));
}
}
return area;
}
``````
1. O(n^2) dp. The optimal solution does not check a rectangle by start/end point. Given a point (i, j), it computes the left boundary, right boundary of the maximal rectangle with height(i,j) incrementally in constant time. The idea is from @morrischen2008.
``````    int maximalRectangle(vector<vector<char>>& matrix) {
int r = matrix.size();
if (!r) return 0;
int c = matrix[0].size(), area = 0;
vector<int> left(c), right(c,c), height(c);
for(int i=0;i<r;i++) {
int cur = 0;
for(int j=0;j<c;j++)
if(matrix[i][j]=='0') {
height[j] = left[j] = 0;
cur = j+1; //left boundary of current row
} else {
left[j] = max(left[j],cur);  //left boundary for height[j]
height[j]++;
}
cur = c;
for(int j=c-1;j>=0;j--) {
if (matrix[i][j]=='0') cur = j;
right[j] = matrix[i][j]=='0'? c:min(right[j],cur);
area = max(height[j]*(right[j]-left[j]),area);
}
}
return area;
}
``````

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