Using Histogram Approach || Stack
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the largest rectangle containing only 1\'s in a binary mat
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the largest rectangle containing only 1\'s in a binary matrix. To solve this, the key idea is to treat each row as the base of a histogram and compute the largest rectangle in that histogram.\n\nFor each row, we create a height array where each element represents the number of consecutive 1\'s encountered in that column (from the top of the matrix to the current row). Once the height array is built for a row, the problem is reduced to finding the largest rectangle in a histogram, which is a classic problem that can be efficiently solved using a monotonic stack.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Building the Height Array:\n   For each row in the matrix:\n   - If the current element is \'1\', we increment the corresponding column in the height array.\n    - If the current element is \'0\', we reset the corresponding column in the height array to 0.\n2. Largest Rectangle in Histogram:\nOnce we have the height array for a row, we compute the largest rectangle in that histogram using the concept of next smaller element and previous smaller element:\n\n   - Next Smaller Element (NSE): For each bar, we find the next bar that is smaller to the right.\n   - Previous Smaller Element (PSE): For each bar, we find the previous bar that is smaller to the left. Using these, we can determine the width of the largest rectangle for each bar in the histogram, and then compute the area.\n3. Maximal Rectangle:\nFor each row, we compute the largest rectangle in the histogram built from the height array and update the maximum area encountered so far.\n\n# Complexity\n- Time complexity: O(n\xD7m) , where n is the number of rows and m is the number of columns in the matrix\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    vector<int> nextSmallerElement(vector<int> &arr, int n)\n{\n    // Write your code here.\n\n    stack<int> s;\n    s.push(-1);\n    vector<int> ans(n);\n\n    for(int i=n-1;i>=0;i--)\n    {\n        int curr=arr[i];\n        while(s.top()!=-1 && arr[s.top()]>=curr)\n        {\n            s.pop();\n        }\n        //ans stack ka top\n        ans[i]=s.top();\n        s.push(i);\n    }\n    return ans;\n}\nvector<int> prevSmallerElement(vector<int> &arr, int n)\n{\n    // Write your code here.\n\n    stack<int> s;\n    s.push(-1);\n    vector<int> ans(n);\n\n    for(int i=0;i<n;i++)\n    {\n        int curr=arr[i];\n        while(s.top()!=-1 && arr[s.top()]>=curr)\n        {\n            s.pop();\n        }\n        //ans stack ka top\n        ans[i]=s.top();\n        s.push(i);\n    }\n    return ans;\n}\n\nint largestArea(vector<int> &arr)\n{\n        int n=arr.size();\n        vector<int> next(n);\n        next=nextSmallerElement(arr,n);\n\n        vector<int> prev(n);\n        prev=prevSmallerElement(arr,n);\n\n        int area=INT_MIN;\n\n        for(int i=0;i<n;i++)\n        {\n          int l=arr[i];\n\n\n          if(next[i]==-1)\n          {\n            next[i]=n;\n          }\n          int b=next[i]-prev[i]-1;\n\n          int newArr=l*b;\n          area=max(area,newArr);\n\n\n        }\n        return area;\n}\npublic:\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        vector<int> height(matrix[0].size(),0);\n\n        int maxi=INT_MIN;\n        for(int i=0;i<matrix.size();i++)\n        {\n            //to create height array\n            for(int j=0;j<height.size();j++)\n            {\n                if(matrix[i][j]==\'1\')\n                {\n                    height[j]++;\n                }\n                else height[j]=0;\n            }\n            maxi=max(maxi,largestArea(height));\n        }\n\n            return maxi;\n    }\n\n};\n```\n![upvote.jpg](https://assets.leetcode.com/users/images/c4df5dbd-c20c-46e2-b24c-2050ce91092d_1725752438.6432638.jpeg)\n
['Array', 'Dynamic Programming', 'Stack', 'Matrix', 'Monotonic Stack', 'C++']