My O(n^3) solution for your reference


  • 16
    U
    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;
            
            
        }
    };

  • 0
    S

    Simple but brilliant solution.


  • 0
    S

    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;
    }
    

    }


Log in to reply
 

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