C++|| Easy to understand clean solution || Mono Stack
\n\n# Approach\n\nQuestion is similar to LC 84 : Largest Rectangle in Histogram. \n\nIn that question we had only one row and all the heights were column.\nHere
\n\n# Approach\n\nQuestion is similar to LC 84 : Largest Rectangle in Histogram. \n\nIn that question we had only one row and all the heights were column.\nHere we have n rows and m columns. simply we apply that logic here for each row. but here we need to take care of one condition if my current cell (matrix[i][j] == 0) then my height will be zero as the vertical length chain will be disrupted. and if matrix[i][j] != 0 that means the vertical length chain will continue without any disruption so we add height[j]+=1;\n  \nLogic for LC 84\n\nArea = length*breadth\nNow for each height which is equivalent to my length in this case.\nI will try to find its maximum breadth both in left and right direction from that height[i]. \nTake   4 5 6 6 1\n\nfor height[1] = 5;\nin left direction: next smallest is 4.\nin right direction: next smallest is 1.\n\nfor heights[2] =6;\nin left direction: next smallest is 5.\nin right direction: next smallest is 1.\n\n**Now if my height is constant and lets say h = 6 then on right if its 5, then it cannot be included in the rectangle of height =6  as heights are different. but if my constant height is 5 and on right my height is 6 then this 6 can be included because i can take length 5 from 6.** \n\nWe can use stack to find the NEXT SMALLEST ELEMENT FROM LEFT AND NEXT SMALLEST ELEMENT FROM RIGHT. We will store the indexes in the stack. \n\n\n\n\n\n\n\n\n\n# Complexity\n- Time complexity:\nO(n^2)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n\n    int solve(vector<int> &heights){\n        int n = heights.size();\n        vector<int> nslr(n),nsrl(n);\n        stack<int> st;\n        for(int i=0;i<n;i++){\n            while(!st.empty() && heights[st.top()] >= heights[i]) st.pop();\n            if(st.empty()) nslr[i] = -1;\n            else nslr[i] = st.top();\n            st.push(i);\n        }\n        while(!st.empty()) st.pop();\n          for(int i=n-1;i>=0;i--){\n            while(!st.empty() && heights[st.top()] >= heights[i]) st.pop();\n            if(st.empty()) nsrl[i] = n;\n            else nsrl[i] = st.top();\n            st.push(i);\n        }\n\n        int ans = 0;\n        for(int i=0;i<n;i++){\n            ans = max(ans,heights[i]*(nsrl[i]-nslr[i]-1));\n        }\n        return ans;\n    }\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        ios_base::sync_with_stdio(false);cin.tie(NULL);\n        int ans = 0;\n        int n = matrix.size();\n        int m = matrix[0].size();\n        vector<int> heights(m,0);\n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                if(matrix[i][j] == \'0\'){\n                    heights[j] = 0;\n                }else{\n                    heights[j]+=1;\n                }\n            }\n            ans = max(ans,solve(heights));\n        }\n        return ans;\n        \n    }\n};\n```\n
['Monotonic Stack', 'C++']