Sharing my straightforward C++ solution with O(n^2) time with explanation


  • 22
    Z
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.empty()){
            return 0;
        }
        int maxRec = 0;
        vector<int> height(matrix[0].size(), 0);
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(matrix[i][j] == '0'){
                    height[j] = 0;
                }
                else{
                    height[j]++;
                }
            }
            maxRec = max(maxRec, largestRectangleArea(height));
        }
        return maxRec;
    }
    
    int largestRectangleArea(vector<int> &height) {
        stack<int> s;
        height.push_back(0);
        int maxSize = 0;
        for(int i = 0; i < height.size(); i++){
            if(s.empty() || height[i] >= height[s.top()]){
                s.push(i);
            }
            else{
                int temp = height[s.top()];
                s.pop();
                maxSize = max(maxSize, temp * (s.empty() ? i : i - 1 - s.top()));
                i--;
            }
        }
        return maxSize;
    }
    

    In order to solve this problem, I use the solution from "Largest Rectangle in Histogram".

    Now I assume you already know how to solve "Largest Rectangle in Histogram".

    We can regard a matrix as many histograms. For example, given a matrix below:

    1 0 1 0

    0 1 0 1

    0 1 1 0

    1 0 1 0

    1 0 1 1

    From top to bottom, we can find these histograms:

    Number 1: 1 0 1 0

    Number 2: 0 1 0 1

    Number 3: 0 2 1 0

    Number 4: 1 0 2 0

    Number 5: 2 0 3 1

    Pass all of these histograms to the function which can solve "Largest Rectangle in Histogram". And then find the maximum one.

    Finally, we get the answer.


  • -2
    K

    this is o(N^3)


  • 0
    I

    I think it's O(n^2) because largestRectangleArea() is called outside inner for-loop.


  • 0
    height.push_back(0);
    

    you should put it in the part where you initialize height.


Log in to reply
 

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