[Java/C++] Explanation going from Brute to Optimal Approach
\nWhat the Question is saying, \nGiven an array of integers heights representing the histogram\'s bar height where the width of each bar is 1, \nreturn the area
```\nWhat the Question is saying, \nGiven an array of integers heights representing the histogram\'s bar height where the width of each bar is 1, \nreturn the area of the largest rectangle in the histogram.\n```\n\nUnderstand this problem with an example;\n**Input:** `heights = [2,1,5,6,2,3]`\n![image](https://assets.leetcode.com/users/images/a844c036-9d8d-4155-a5fa-8f565822109d_1643426746.9005287.png)\n\nLet\'s understand how we calculate this, let\'s took on index 4 height is 2. If we go to the left and see where the height is less then 2 and i.e. at index 1. So, that becomes the left Boundary. Similarly if we go to right and see where the height is less then 2 & i.e. at index 6 [which is end of the array].\n\nNow we have left & right boundary the area could be find out by height * width. And width will get by (right - left - 1) in case of 4 that will be 6 - 1 - 1 = 4. And we know the height already i.e. 2.\n\nThe Area we get is 2 * 4 i.e. 8\n\n![image](https://assets.leetcode.com/users/images/c49249ab-e50d-487a-8761-e130f41ee36c_1643428100.9047763.png)\n\nThe main idea here would be how to find **left boundary & right boundary** for every index. The **brute way** is using an **ARRAY**\n`For left boundary array:`\n* Start with index 1, (left[0] = -1)\n* For each index -> go to left & find the nearest index where height [index] < height[curr]\n* Start with index 1,\n* Eg : Index 1 : left[1] = -1\n\n`For right boundary array:`\n* Start with index n - 2 right[n - 1] = n\n* For each index -> go to right & find the nearest index where height[index] < height[curr]\n* Start with index n - 2\n* Eg : Index 2 : right[2] = 4\n\nI hope you got the point and let\'s code this brute force Approach then we move to optimal Approach:\n**Java**\n```\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        int n = heights.length;\n        if(n == 0) return 0; // Base Condition\n        int maxArea = 0;\n        int left[] = new int[n]; //fill left boundary\n        int right[] = new int[n]; // fill right boundary\n        \n        left[0] = -1;\n        right[n - 1] = n;\n        \n        for(int i = 1; i < n; i++){\n            int prev = i - 1; // previous for comparing the heights\n            while(prev >= 0 && heights[prev] >= heights[i]){\n                prev = left[prev]; // we have done this to minimise the jumps we make to the left\n            }\n            left[i] = prev;\n        }\n        // Similarly we do for right\n        for(int i = n - 2; i >= 0; i--){\n            int prev = i + 1; \n            while(prev < n && heights[prev] >= heights[i]){\n                prev = right[prev]; \n            }\n            right[i] = prev;\n        }\n        // once we have these two arrays fill we need width & area\n        for(int i = 0; i < n; i++){\n            int width = right[i] - left[i] - 1;\n            maxArea = Math.max(maxArea, heights[i] * width);\n        }\n        return maxArea;\n        \n    }\n}\n```\n**C++**\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int n = heights.size();\n        if(n == 0) return 0; // Base Condition\n        int maxArea = 0;\n        vector<int> left(n); //fill left boundary\n        vector<int> right(n); // fill right boundary\n        \n        left[0] = -1;\n        right[n - 1] = n;\n        \n        for(int i = 1; i < n; i++){\n            int prev = i - 1; // previous for comparing the heights\n            while(prev >= 0 && heights[prev] >= heights[i]){\n                prev = left[prev]; // we have done this to minimise the jumps we make to the left\n            }\n            left[i] = prev;\n        }\n        // Similarly we do for right\n        for(int i = n - 2; i >= 0; i--){\n            int prev = i + 1; \n            while(prev < n && heights[prev] >= heights[i]){\n                prev = right[prev]; \n            }\n            right[i] = prev;\n        }\n        // once we have these two arrays fill we need width & area\n        for(int i = 0; i < n; i++){\n            int width = right[i] - left[i] - 1;\n            maxArea = max(maxArea, heights[i] * width);\n        }\n        return maxArea;\n    }\n};\n```\nANALYSIS :\n* **Time Complexity :-** BigO(N^2)\n\n* **Space Complexity :-** BigO(N)\n\nNow, let\'s see our Optimize Approach i.e. **Using Stack**\nSo, what we do is we take a stack & keep on adding the indexes in the stack till we get a increasing sequence. Once the sequence becomes decreasing we need to pop the element and find the area `[That\'s the basic idea behind the stack]`\n\nSo, let\'s take the stack and we are at index 1. The height of current is less than that of top of stack which is the 0th index. As the height is decreasing. So, what we do here is find the area for elements in stack\n![image](https://assets.leetcode.com/users/images/7688de81-3901-4177-92b9-416735c81ab2_1643429827.2194455.png)\n\nNow, to find the area we pop the element from stack & then for that element the area becomes **height[top] * curr i.e. 1**\nIf the stack becomes empty i.e. if this is the only element present for that we find the width and multiply with the height of top element `[width would be curr - stack.peek - 1]` where curr is right & stack.peek() is left\n\nFor this case we **pop "0"** and stack becomes **empty**, so the area becomes **height[0] * curr = 2 * 1 = 2.** So, till now maxArea we have found is 2\n\n![image](https://assets.leetcode.com/users/images/b4251cd2-8015-48eb-9ed4-b5bf6ffb9919_1643431407.4375658.png)\n\nWe will do this procedure for all the element\'s and we will get the **maxArea i.e. 10**\n\n*I hope you got the idea,* **So, let\'s code it up:**\n**Java**\n```\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        int n = heights.length;\n        int maxArea = 0;\n        Stack<Integer> st = new Stack<>();\n        \n        for(int i = 0; i <= n; i++){\n            int currHeight = i == n ? 0 : heights[i];\n            // check if currHeight becomes greater then height[top] element of stack. we do a push because it\'s an increasing sequence\n            // otherwise we do pop and find area, so for that we write a while loop\n            while(!st.isEmpty() && currHeight < heights[st.peek()]){\n                int top = st.pop(); // current element on which we are working\n                // now we need width & area\n                int width = st.isEmpty() ? i : i - st.peek() - 1; // width differ, if stack is empty or not empty after we pop the element\n                int area = heights[top] * width; // current height * width\n                maxArea = Math.max(area, maxArea);\n            }\n            // if it doesn\'t enter in while loop, it means it\'s an increasing sequence & we need to push index\n            st.push(i);\n        }\n        return maxArea;\n    }\n}\n```\n**C++**\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int n = heights.size();\n        int maxArea = 0;\n        stack<int> st;\n        \n        for(int i = 0; i <= n; i++){\n            int currHeight = i == n ? 0 : heights[i];\n            // check if currHeight becomes greater then height[top] element of stack. we do a push because it\'s an increasing sequence\n            // otherwise we do pop and find area, so for that we write a while loop\n            while(!st.empty() && currHeight < heights[st.top()]){\n                int top = st.top(); st.pop(); // current element on which we are working\n                // now we need width & area\n                int width = st.empty() ? i : i - st.top() - 1; // width differ if we stack is empty or not empty after we pop the element\n                int area = heights[top] * width; // current height * width\n                maxArea = max(area, maxArea);\n            }\n            // if it doesn\'t enter in while loop, it means it\'s an increasing sequence & we need to push index\n            st.push(i);\n        }\n        return maxArea;\n    }\n};\n```\nANALYSIS :\n* **Time Complexity :-** BigO(N)\n\n* **Space Complexity :-** BigO(N)
['C', 'Java']