Simple Explanation | O(n^2) |  C++ | Derived from Maximum Area in Histogram
Prerequisite : Please solve this problem first for better understanding Maximum Area in Histogram\n\n\nclass Solution {\npublic:\n    \n\t// This function accep
**Prerequisite** : Please solve this problem first for better understanding [Maximum Area in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)\n\n```\nclass Solution {\npublic:\n    \n\t// This function accepts height of histograms and calculates the maximum area of reactange\n\t// i.e this function is the solution of problem mentioned in the above link\n    int maxAreaHistogram(vector<int> &arr)\n    {\n        int n = arr.size();\n        vector<int> rig(n, n), lef(n, -1);        // rig and lef vectors stores the first index in right and left whose height is less\n        stack<int> s;\n        \n\t\t// storing the right index\n        for(int i=n-1;i>=0;i--)\n        {\n            while(!s.empty() && arr[s.top()]>=arr[i]) s.pop();\n            \n            if(!s.empty()) rig[i] = s.top();\n            s.push(i);\n        }\n\t\t\n        while(!s.empty()) s.pop();\n        \n\t\t// storing the left index\n        for(int i=0;i<n;i++)\n        {\n            while(!s.empty() && arr[s.top()]>=arr[i]) s.pop();\n            if(!s.empty()) lef[i] = s.top();\n            s.push(i);\n        }\n        \n        int ans = 0;\n\t\t// area =  width x height = ( rig[i] - lef[i]-1 )  x ( arr[i] )\n        for(int i=0;i<n;i++)\n            ans = max(ans, arr[i]*(rig[i]-lef[i]-1));\n        \n        return ans;\n    }\n    \n\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        int n = matrix.size();\n        if(n==0) return 0;\n        int m = matrix[0].size();\n        \n        vector<vector<int> > mat(n, vector<int>(m));\n        \n\t\t// Converting char matrix to integer matrix\n        for(int i=0;i<n;i++)\n            for(int j=0;j<m;j++)\n                mat[i][j] = int(matrix[i][j]-\'0\');\n                \n\t\t// Calculating height of histogram for each row, but note that whenever we encounter zero height will become zero\n        for(int i=1;i<n;i++)\n            for(int j=0;j<m;j++)\n                if(mat[i][j])\n                    mat[i][j] += mat[i-1][j];\n\n        int ans = 0;\n\t\t\n\t\t// now solving maxAreaHistogram for considering each row, and maximum of each level will be our ans\n        for(int i=0;i<n;i++)\n            ans = max(ans, maxAreaHistogram(mat[i]) );\n        return ans;\n    }\n};\n```
['Stack', 'C']