Leetcode POTD
Approach :\n\n1. Here we will use the logic of largest rectangular area in a histogram .\n2.  In this logic we will find the next and prev smallest element from
Approach :\n\n1. Here we will use the logic of largest rectangular area in a histogram .\n2.  In this logic we will find the next and prev smallest element from the array by traversing it using stack .\n3.   Now we will find the max rectangle area by converting it into largest rectangular histogram row by row and update te max rectangle area.\n\n\nThis approach is inspired by Love babbar.\n\nCode in C++\n\n```\nclass Solution {\n    \n    vector<int>next_small(vector<int>&arr){\n        int n=arr.size();\n        stack<int>st;\n        \n        st.push(-1);\n        \n        vector<int>ans(n);\n        \n        for(int i=n-1;i>=0;i--){\n            int curr=arr[i];\n            \n            while(st.top()!=-1 && arr[st.top()]>=curr){\n                st.pop();\n            }\n            \n            \n            // smaller element found\n            \n            ans[i]=st.top();\n            \n            st.push(i);\n        }\n        \n        return ans;\n    }\n    \n    vector<int>prev_small(vector<int>&arr ){\n        int n=arr.size();\n        stack<int>st;\n        \n        st.push(-1);\n        \n        vector<int>ans(n);\n        \n        for(int i=0;i<n;i++){\n            int curr=arr[i];\n            \n            while(st.top()!=-1 && arr[st.top()]>=curr){\n                st.pop();\n            }\n            \n            \n            // smaller element found\n            \n            ans[i]=st.top();\n            \n            st.push(i);\n        }\n        \n        return ans;\n    }\n    \n    int largest_area(vector<int>&heights){\n        int n=heights.size();\n        \n        vector<int>next(n);\n        next=next_small(heights);\n        \n        vector<int>prev(n);\n        prev=prev_small(heights);\n        int maxi=0;\n        \n        for(int i=0;i<n;i++){\n            int length=heights[i];\n            \n            if(next[i]==-1){\n                next[i]=n;\n            }\n            int breadth=next[i]-prev[i]-1;\n            \n            \n            int area=length*breadth;\n            maxi=max(maxi,area);\n            \n        }\n        \n        return maxi;\n    }\npublic:\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        \n        int maxi=0;\n        \n        vector<int>height(matrix[0].size(),0);\n        \n        for(int i=0;i<matrix.size();i++){\n            for(int j=0;j<height.size();j++){\n                if(matrix[i][j]==\'1\'){\n                    height[j]++;\n                }\n                else{\n                    height[j]=0;\n                }\n               \n            }\n             maxi=max(maxi,largest_area(height));\n        }\n        \n        return maxi;\n    }\n};\n\n```
['Stack', 'C', 'Monotonic Stack']