Aditya verma Solution | C++ | Maximal Rectangle
Aditya Verma Solutions\n\nQ1.\n85. Maximal Rectangle\nhttps://leetcode.com/problems/maximal-rectangle/\n\n\nclass Solution {\npublic:\nint largestRectangleArea(
# Aditya Verma Solutions\n\n**Q1.**\n***85. Maximal Rectangle***\nhttps://leetcode.com/problems/maximal-rectangle/\n\n```\nclass Solution {\npublic:\nint largestRectangleArea(vector<int>& heights) {\n    int n= heights.size();\n    vector<int> left,right;\n    stack<pair<int,int>> s1,s2;\n    int pseudo_index =-1;\n    int pseudo_index1 =n;\n    for (int i=0;i<n;i++)\n    {\n      if (s1.size()==0)\n      {\n        left.push_back(pseudo_index);\n      }\n      else if (s1.size()>0 && s1.top().first<heights[i])\n      {\n        left.push_back(s1.top().second);\n      }\n      else if (s1.size()>0 && s1.top().first>=heights[i])\n      {\n         while(s1.size()>0 && s1.top().first>=heights[i])\n         {\n           s1.pop();\n         }\n        if (s1.size()==0)\n        {\n          left.push_back(pseudo_index);\n        }\n        else\n        {\n          left.push_back(s1.top().second);\n        }\n      }\n      s1.push({heights[i],i});\n    }\n    for (int i=n-1;i>=0;i--)\n    {\n      if (s2.size()==0)\n      {\n        right.push_back(pseudo_index1);\n      }\n      else if (s2.size()>0 && s2.top().first<heights[i])\n      {\n        right.push_back(s2.top().second);\n      }\n      else if (s2.size()>0 && s2.top().first >= heights[i])\n      {\n        while(s2.size()>0 && s2.top().first >= heights[i])\n        {\n          s2.pop();\n        }\n        if (s2.size()==0)\n        {\n          right.push_back(pseudo_index1);\n        }\n        else\n        {\n          right.push_back(s2.top().second);\n        }\n      }\n      s2.push({heights[i],i});\n    }\n    reverse(right.begin(),right.end());\n    int m=INT_MIN;\n    for (long long i=0;i<n;i++)\n    {\n      m=max(m,(right[i]-left[i]-1)*heights[i]);// taking max after finding area\n    }\n    return m;\n    }\n\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        int m=matrix.size();\n        if(m==0) return 0;\n        int n=matrix[0].size(), result=0;\n        vector<int> histogram(n, 0);\n        \n        for(int i=0; i<m; i++){\n            for(int j=0; j<n; j++){\n                if(matrix[i][j]==\'1\')\n                    histogram[j]+=1;\n                else\n                    histogram[j]=0;\n            }\n            \n            result = max(result, largestRectangleArea(histogram));\n            // cout<<result<<" ";\n        }\n        return result;\n    }\n};\n\n```\n\n**Q2.**\n***84. Largest Rectangle in Histogram***\nhttps://leetcode.com/problems/largest-rectangle-in-histogram/\n\n```\nclass Solution\n{\n\tpublic:\n\t\tint getMaxArea(vector<int> &arr, int n)\n\t\t{\n\t\t\tvector<int> left, right;\n\t\t\tstack<pair<int, int>> s1, s2;\n\t\t\tint pseudo_index = -1;\n\t\t\tint pseudo_index1 = n;\n\t\t\tfor (int i = 0; i < n; i++)\n\t\t\t{\n\t\t\t\tif (s1.size() == 0)\n\t\t\t\t{\n\t\t\t\t\tleft.push_back(pseudo_index);\n\t\t\t\t}\n\t\t\t\telse if (s1.size() > 0 && s1.top().first < arr[i])\n\t\t\t\t{\n\t\t\t\t\tleft.push_back(s1.top().second);\n\t\t\t\t}\n\t\t\t\telse if (s1.size() > 0 && s1.top().first >= arr[i])\n\t\t\t\t{\n\t\t\t\t\twhile (s1.size() > 0 && s1.top().first >= arr[i])\n\t\t\t\t\t{\n\t\t\t\t\t\ts1.pop();\n\t\t\t\t\t}\n\n\t\t\t\t\tif (s1.size() == 0)\n\t\t\t\t\t{\n\t\t\t\t\t\tleft.push_back(pseudo_index);\n\t\t\t\t\t}\n\t\t\t\t\telse\n\t\t\t\t\t{\n\t\t\t\t\t\tleft.push_back(s1.top().second);\n\t\t\t\t\t}\n\t\t\t\t}\n\n\t\t\t\ts1.push({ arr[i], i });\n\t\t\t}\n\n\t\t\tfor (int i = n - 1; i >= 0; i--)\n\t\t\t{\n\t\t\t\tif (s2.size() == 0)\n\t\t\t\t{\n\t\t\t\t\tright.push_back(pseudo_index1);\n\t\t\t\t}\n\t\t\t\telse if (s2.size() > 0 && s2.top().first < arr[i])\n\t\t\t\t{\n\t\t\t\t\tright.push_back(s2.top().second);\n\t\t\t\t}\n\t\t\t\telse if (s2.size() > 0 && s2.top().first >= arr[i])\n\t\t\t\t{\n\t\t\t\t\twhile (s2.size() > 0 && s2.top().first >= arr[i])\n\t\t\t\t\t{\n\t\t\t\t\t\ts2.pop();\n\t\t\t\t\t}\n\n\t\t\t\t\tif (s2.size() == 0)\n\t\t\t\t\t{\n\t\t\t\t\t\tright.push_back(pseudo_index1);\n\t\t\t\t\t}\n\t\t\t\t\telse\n\t\t\t\t\t{\n\t\t\t\t\t\tright.push_back(s2.top().second);\n\t\t\t\t\t}\n\t\t\t\t}\n\n\t\t\t\ts2.push({ arr[i], i });\n\t\t\t}\n\n\t\t\treverse(right.begin(), right.end());\n\t\t\tint m = INT_MIN;\n\t\t\tfor (int i = 0; i < n; i++)\n\t\t\t{\n\t\t\t\tint s = (right[i] - left[i] - 1) *arr[i];\n\t\t\t\tm = max(m, s);\t// taking max after finding area\n\t\t\t}\n\n\t\t\treturn m;\n\t\t}\n\n\tint largestRectangleArea(vector<int> &heights)\n\t{\n\t\tint n = heights.size();\n\t\treturn getMaxArea(heights, n);\n\n\t}\n};\n
['Stack', 'C++']