C++ 2 Solutions | Better to Optimal with Explanation | Easy to Understand
Approach 1\n\n\nint maximalRectangle(vector<vector<char>>& matrix) {\n//base cases\n        int n = matrix.size();\n        if(n == 0) return 0;\n        int m 
## Approach 1\n\n```\nint maximalRectangle(vector<vector<char>>& matrix) {\n//base cases\n        int n = matrix.size();\n        if(n == 0) return 0;\n        int m = matrix[0].size();\n        if(n + m == 2) return matrix.front().front() == \'1\';\n\t\t\n\t\t//dp to store max number of adjacent 1s on left for each matrix[ i ][ j ]\n        vector<vector<int>> dp(n+1,vector<int>(m+1,0));\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n                if(matrix[i-1][j-1] != \'0\')\n                  dp[i][j] = 1 + dp[i][j-1];\n                // cout<<dp[i][j]<<" ";\n            }\n            // cout<<endl;\n        }\n        \n\t\t\n\t\t//variable to store answer\n        int area = 0;\n\t\t\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n\t\t\t//variable to store current width of rectangle of size 1 * dp[i][j]\n                int width = dp[i][j];\n                int k = i-1;\n                int height = 1;\n                area = max(area,width * height);\n\t\t\t\t\n\t\t\t\t//now we\'ll start moving upwards as long as we are inside the matrix\n\t\t\t\t//ans change the height ans width accordingly to find the largest\n\t\t\t\t//area which can be achieved including current element\n\t\t\t\t//height always increases as we go up, width of rectangle till that height changes\n\t\t\t\t//to minimum no. of left 1s for every upward element\n                while(k > 0 and dp[k][j] > 0)\n                {\n                    height++;\n                    width = min(width,dp[k--][j]);\n\t\t\t\t\t//for every acceptable height, we check if it can be our answer\n                    area = max(width * height,area);\n                }\n            }\n        }\n        \n        return area;\n    }\n```\n\n**Time Complexity :** O(n * m * n)\n**Space Complexity :** O(n * m)\n\n## Approach 2\n\nThe second method utilizes the concept of the [Largest Reactangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/) to compute the largest rectangle for a given row efficiently.\n\n```\n//code to find largest rectangle in histogram\nint largestRectangle(vector<int> &dp)\n    {\n        stack<int> st;\n        st.push(-1);\n        int max_area = 0;\n        for(int i=0;i<=dp.size();i++)\n        {\n            int val = (i == dp.size()) ? -1 : dp[i];\n            while(st.top() != -1 and dp[st.top()] > val)\n            {\n                int height = dp[st.top()];\n                st.pop();\n                int width = i - st.top() - 1;\n                max_area = max(max_area,width * height);\n            }\n            st.push(i);\n        }\n        return max_area;\n    }\n\t\n\tint maximalRectangle(vector<vector<char>>& matrix) {\n\t\t//base cases\n        int n = matrix.size();\n        if(n == 0) return 0;\n        int m = matrix[0].size();\n        if(n + m == 2) return matrix[0][0] == \'1\';\n        \n\t\t//program to calculate maximum height for current element\n        vector<int> dp(m,0);\n        \n        int res = 0;\n        \n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<m;j++)\n            {\n\t\t\t\t//if current 0 then total height is 0 else increase the previous height\n                if(matrix[i][j] == \'0\') dp[j] = 0;\n                else dp[j]++;\n            }\n            res = max(res,largestRectangle(dp));\n        }\n        \n        return res;\n    }\n```\n\n**Time Complexity :** O(n * (m + n) )\n**Space Complexity :** O(n + n) [dp array + stack to find largest rectangle]\n\nDO upvote, if it helped you :)
['Dynamic Programming', 'Stack']