My 26ms C++ O(m^2*n) algorithm with O(mn) space


  • 0
    V
    class Solution {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            if(matrix.size() == 0) {
                return 0;
            }
            int maxArea=0;
            vector<vector<int>> length(matrix.size(), vector<int>(matrix[0].size(), 0));
            vector<vector<int>> breadth(matrix.size(), vector<int>(matrix[0].size(), 0));
            if(matrix[0][0] == '1') {
                length[0][0] = 1;
                breadth[0][0] = 1;
                maxArea = 1;
            }
            for(int i=1; i<matrix.size(); i++) {
                if(matrix[i][0] == '1') {
                    length[i][0] = 1;
                    breadth[i][0] = breadth[i-1][0] + 1;
                    maxArea = max(maxArea, breadth[i][0]);
                }
            }
            for(int i=1; i<matrix[0].size(); i++) {
                if(matrix[0][i] == '1') {
                    length[0][i] = length[0][i-1] + 1;
                    breadth[0][i] = 1;
                    maxArea = max(maxArea, length[0][i]);
                }
            }
            for(int i=1; i<matrix.size(); i++) {
                for(int j=1; j<matrix[0].size(); j++) {
                    if(matrix[i][j] == '1') {
                        length[i][j] = length[i][j-1] + 1;
                        breadth[i][j] = breadth[i-1][j] + 1;
                        maxArea = max(maxArea, getMaxArea(i, j, length, breadth));
                    }
                }
            }
            return(maxArea);
        }
        
        int getMaxArea(int rPos, int cPos, vector<vector<int>> &length, vector<vector<int>> &breadth) {
            int maxBreadth = breadth[rPos][cPos];
            int currBreadth = 1;
            int maxArea = 1;
            int upperLengthBound = length[rPos][cPos];
            for(int k=rPos; k>rPos-maxBreadth; k--) {
                if(length[k][cPos] < upperLengthBound) {
                    upperLengthBound = length[k][cPos];
                }
                maxArea = max(maxArea, (currBreadth * upperLengthBound));
                currBreadth+=1;
            }
            return(maxArea);
        }
    };
    

Log in to reply
 

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