# My O(n^3) solution for your reference

• ``````class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
int num_i=matrix.size();
if (num_i==0) return 0;
int num_j=matrix[0].size();
if (num_j==0) return 0;
vector<vector<int>> max_x(num_i,vector<int>(num_j,0));  //number of consecutive 1s to the left of matrix[i][j], including itself

int area=0;
for (int i=0;i<num_i;i++){
for (int j=0;j<num_j;j++){
if (matrix[i][j]=='1'){
if (j==0) max_x[i][j]=1;
else max_x[i][j]=max_x[i][j-1]+1;
int y=1;
int x=num_j;
while((i-y+1>=0)&&(matrix[i-y+1][j]=='1')){
x=min(x, max_x[i-y+1][j]);
area=max(area,x*y);
y++;
}
}
}
}

return area;

}
};``````

• Simple but brilliant solution.

• Same as above C++, written in Java.
public class Solution {
public int maximalRectangle(char[][] matrix) {

``````    int area = 0;
int numRows = matrix.length;
if (numRows == 0) return 0;
int numCols = matrix[0].length;
if (numCols == 0) return 0;
int [][] rowArea = new int[numRows][numCols];
for (int i = 0; i < numRows; i++) { // y
for (int j = 0; j < numCols; j++) {
if (matrix[i][j] == '0') continue;
else {
if (j == 0) rowArea[i][j] = 1;
else {
rowArea[i][j] = rowArea[i][j-1] + 1;
}
int y = 1;
int x = numCols;
while(i-y+1 >= 0 && rowArea[i-y+1][j] > 0) {
x = Math.min(x, rowArea[i-y+1][j]);
area = Math.max(area, x*y);
y++;
}
}
}
}
return area;
}
``````

}

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