My histogram based solution. O(n^2) time, O(n) space, with detailed explanation


  • 0
    D

    /* The basic idea is to scan the matrix row by row and update the histogram for each row. From top to bottom, assuming the current row is the bottom row of the maximal rectangle, calculating the maximal rectangle area using the histogram info. The hist array can be updated based on the results from the previous row. If matrix[i][j]=1, then hist[j] = hist[j]+1, otherwise 0.
    To calculate the maximal area using the histogram, a stack method is used. Everytime, a current bar is higher than the top one of the stack, push it in the stack; otherwise, pop up the top element and update the maximal area;
    A dummy "0-height" element is added to the bottom of the stack to avoid empty-stack checking and another dummy "0-height" element is added to hist to pop up all the elements in the stack at the end of the scan.
    */

    class Solution {
    public:
        int maximalRectangle(vector<vector<char> > &matrix) {
            const int row = matrix.size();
            if(!row) return 0;  // if the matrix is empty, return 0;
            const int col = matrix[0].size();
            if(!col) return 0;  
            
            int i,j, maxArea=0, left;
            int heights[col+1];
            vector<pair<int, int>> hist;
            hist.reserve(col+2);
            
            fill_n(heights, col+1, 0); // initialize hist to all zero, note that hist[col] is a dummy element that is used to empty the hist stack when updating the maximal area
    
            for(i=0; i<row; i++)
            { // scan all the rows from top to bottom
                // first update heights
                for(j=0;j<col;j++)
                {
                    heights[j] = (matrix[i][j]=='0')? 0:heights[j]+1;
                }
                
                // update maxArea based on histograph
                hist.clear(); 
                hist.push_back(make_pair(0,0)); // add a dummy element (with the height of -1) at the bottom of the stack to guarantee the stack is not empty; 
                for(j=0;j<=col;j++)
                {
                    if(heights[j]>hist.back().first)
                    { // if the current bar is larger than the areas in the stack can continue
                        hist.push_back(make_pair(heights[j], j));
                    }
                    else
                    { // otherwise, the top area in the stack is terminated, calculate the area and update the maximal area if needed
                        left = j;
                        while(heights[j]<hist.back().first) // note "<" is use, but left needs to be initialized to the current index
                        {
                            left = hist.back().second;
                            maxArea = max(maxArea, hist.back().first *(j-left));
                            hist.pop_back();
                        }
                        hist.push_back(make_pair(heights[j], left)); // note, the index (pair.second) is updated with the one of the last pop-up elemenet
                    }
                }
            }
            return maxArea;
    
        }
    };
    

    // A concise version

    class Solution {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            int M, N, i,j, res = 0, left;
            if( !(M= matrix.size()) || !(N= matrix[0].size()) ) return 0;
            int hist[N+1];
            fill_n(hist, N, 0);
            vector<pair<int, int>> hS;
            hS.reserve(N);
    
            for(i=0; i<M; ++i)
            for(j=0, hS.clear(),hS.push_back(make_pair(0,-1)); j<=N;  ++j)
            {
                hist[j] = (j==N) || matrix[i][j]== '0'? 0: (hist[j]+1);
                left = j;
                while(hist[j]<hS.back().first)
                {
                    left = hS.back().second;
                    res = max(res, hS.back().first*(j-hS.back().second));
                    hS.pop_back();
                }
                hS.push_back(make_pair(hist[j], left));
            }
            return res;
        
        }
    };

  • 0
    R

    I do not understand why you think it is O(n^2). it is anyway 3 loops


Log in to reply
 

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