[C++] Simple Solution | Brute Force ▶️ Optimal | W/ Explanation
APPROACH 1 : BRUTE FORCE\n\n A Brute force approach would be to one by one consider all bars as starting points and calculate area of all rectangles starting wi
**APPROACH 1 : BRUTE FORCE**\n\n* A Brute force approach would be to one by one consider all bars as starting points and calculate area of all rectangles starting with every bar. \n* Finally return maximum of all possible areas. \n\n**Time complexity :** O(n^2)\n\n* We can use Divide and Conquer to solve this in O(nLogn) time. \n* The idea is to find the minimum value in the given array. \n* Once we have index of the minimum value, the max area is maximum of following three values :\n          1. Maximum area in left side of minimum value (w/o including the min value) \n          2. Maximum area in right of minimum value (not including the min value) \n          3. Number of bars multiplied by minimum value. \n* The areas on left & right can be calculated recursively. \n* If we use linear search to find the minimum value, then the worst case time complexity of this algorithm becomes O(n^2). (In the worst case, there are always ```n-1``` elements on one-side & 0 elements on the other)\n\n**APPROACH 2 : Using Left-Smaller & Right-Smaller Arrays**\n\n* First we will take two arrays left_smaller[] and right_smaller[] and initialize it with -1 and n respectively.\n* For every index, we will store the index of previous smaller and next smaller element in ```left_smaller``` and ```right_smaller``` arrays respectively. - ```O(n)``` time\n*  Now for every element we will calculate area by taking this ith element as the smallest in the range left_smaller[i] and right_smaller[i] and multiplying it with the difference of left_smaller[i] and right_smaller[i].\n*  Each time we update the max_area according to the area obtained in the previous step.\n\n**Time Complexity :** O(n) - 3-pass \n\n**Space Complexity :** O(n)\n\n**Code :**\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int n = heights.size();\n        stack<int> s; \n        vector<int> left_bound(n,0),right_bound(n,n); \n        for(int i=0;i<n;i++) {\n            while(!s.empty() && heights[i]<=heights[s.top()])  s.pop();\n            if(s.empty())  left_bound[i]=0;\n            else  left_bound[i] = s.top()+1;\n\t\t\t\n            s.push(i);\n        }\n        while(!s.empty()) s.pop();\n        for(int i=n-1; i>=0; i--)  {\n            while(!s.empty() && heights[i]<=heights[s.top()])  s.pop();\n            if(s.empty()) right_bound[i] = n-1;\n            else  right_bound[i] = s.top()-1;\n            s.push(i);\n        }\n        int maxi = 0, area;\n        for(int i=0; i<n; i++) {\n            area = (right_bound[i]-left_bound[i]+1)*heights[i];\n            maxi = max(maxi, area);\n        }\n        return maxi; \n    }\n};\n```\n\n**APPROACH 3 : Using Only Stack**\n\n* For every bar \u2018x\u2019, we calculate the area with \u2018x\u2019 as the smallest bar in the rectangle.\n* We need to know index of the first smaller (smaller than \u2018x\u2019) bar on left of \u2018x\u2019 and index of first smaller bar on right of \u2018x\u2019.\n* We traverse all bars from left to right, maintain a stack of bars. \n* Every bar is pushed to stack once. \n* A bar is popped from stack when a bar of smaller height is seen. \n* When a bar is popped, we calculate the area with the popped bar as smallest bar - the current index tells us the \u2018right index\u2019 and index of previous item in stack is the \u2018left index\u2019.\n\n**ALGORITHM :**\n* Create an empty stack.\n* Start from first bar, and do following for every bar \u2018hist[i]\u2019 where \u2018i\u2019 varies from 0 to n-1. \n\t\t1.  If stack is empty or hist[i] is higher than the bar at top of stack, then push \u2018i\u2019 to stack. \n\t\t2.  If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. \n\t\t3.  Let the removed bar be hist[tp]. \n\t\t4.  Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the \u2018left index\u2019 is previous (previous to tp) item in stack and \u2018right index\u2019 is \u2018i\u2019 (current index).\n Until the stack becomes empty, one by one remove all bars from stack and do steps 2-4 of the previous step for every removed bar.\n \n **Time Complexity :** O(n) - One-pass\n \n**Code :**\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int ans=INT_MIN, area_with_top=0, top=0, i=0, n=heights.size();\n        stack<int> s;\n        \n        while(i<n){\n            if(s.empty() || heights[s.top()]<=heights[i]) s.push(i++);\n            else{\n                top = s.top(); s.pop();\n                area_with_top = heights[top]*(s.empty() ? i : i-s.top()-1);\n                ans = max(ans, area_with_top);\n            }\n        }\n        \n        while(!s.empty()){\n            top = s.top(); s.pop();\n            area_with_top = heights[top]*(s.empty() ? i : i-s.top()-1);\n            ans = max(ans, area_with_top);\n        }  \n        return ans;\n    }\n};\n```\n\n**Do upvote if you like my solution :)**\n\n\n
['Stack', 'C', 'C++']