Largest Histogram + Bottom Up filling O(n^2) solution
\nBased on Largest area rectangle in  Histogram ...\n\n\nclass Solution {\npublic:\n    \n    int hist(vector<int> &height){\n        \n        if(height.size()
\nBased on Largest area rectangle in  Histogram ...\n\n```\nclass Solution {\npublic:\n    \n    int hist(vector<int> &height){\n        \n        if(height.size()==0){return 0;}\n        if(height.size()==1){return height[0];}\n        int ans=0;\n        stack<int> s;\n        for(int i=0;i<height.size();i++){\n            if(s.empty()||height[i]>=height[s.top()]){\n                s.push(i);\n            }\n            else {\n                int temp=s.top();\n                s.pop();\n                if(s.empty()){\n                    ans=max(ans,height[temp]*i);\n                }\n                else{\n                    ans=max(ans,height[temp]*(i-s.top()-1));\n                }\n                i--;\n            }\n        }\n        int i=height.size();\n        while(!s.empty()){\n            int temp=s.top();\n                s.pop();\n                if(s.empty()){\n                    ans=max(ans,height[temp]*i);\n                }\n                else{\n                    ans=max(ans,height[temp]*(i-s.top()-1));\n                }\n        }\n        return ans;\n        \n    }\n    \n    \n    int maximalRectangle(vector<vector<char>>& matrix) {\n        if(matrix.size()==0){return 0;}\n        vector<vector<int>> heights(matrix.size(),vector<int> (matrix[0].size(),0));\n        int n=matrix.size();\n        for(int i=0;i<n;i++){\n            heights[i][matrix[i].size()-1]= matrix[i][matrix[i].size()-1]==\'0\'?0:1;\n            \n            for(int j=matrix[i].size()-2;j>=0;j--){\n                if(matrix[i][j]==\'0\'){heights[i][j]=0;}\n                else{\n                    heights[i][j]=heights[i][j+1]+1;\n                }\n            }\n        }\n        \n        int ans=0;\n      \n        for(int j=0;j<matrix[0].size();j++){\n            vector<int> temp;\n              int mini =INT_MAX;\n            for(int i=0;i<matrix.size();i++){\n                mini=min(mini,heights[i][j]);\n                temp.push_back(heights[i][j]);\n            }\n            ans=max(ans,hist(temp));\n            j+=mini;\n        }\n        return ans;\n        \n    }\n};\n```
[]