TWO APPROACHES USING LEFT AND RIGHT MINIMUM || SINGLE PASS || O( N ) ✅✅
Approach 1\n\n### Intuition:\nWe can solve this problem using a stack to efficiently calculate the left and right boundaries of each bar.\n\n### Approach:\n1. U
## Approach 1\n\n### Intuition:\nWe can solve this problem using a stack to efficiently calculate the left and right boundaries of each bar.\n\n### Approach:\n1. Use two passes:\n   - In the first pass, calculate the left boundary of each bar.\n   - In the second pass, calculate the right boundary of each bar and simultaneously update the maximum area.\n2. To calculate the left boundary:\n   - Use a stack to store the indices of bars.\n   - Traverse the histogram from left to right.\n   - For each bar, pop elements from the stack until finding a smaller bar.\n   - The left boundary of the current bar is the index at the top of the stack.\n3. To calculate the right boundary and update the maximum area:\n   - Repeat the same process as above, but traverse the histogram from right to left.\n   - For each bar, pop elements from the stack until finding a smaller bar.\n   - The right boundary of the current bar is the index at the top of the stack.\n   - Update the maximum area by computing the area of the rectangle formed by the current bar.\n\n### Explanation:  \n- We maintain two arrays, left[] and right[], to store the left and right boundaries of each bar.\n- In the first pass, we calculate the left boundaries using a stack.\n- In the second pass, we calculate the right boundaries and simultaneously update the maximum area.\n- The maximum area is updated by computing the area of the rectangle formed by each bar.\n\n### Time Complexity  \nO(n), where n is the number of bars in the histogram.\n\n### Space Complexity:\nO(n), used for the stack and left/right arrays.\n\n### Example with Clear Explanation:\nConsider the histogram [2,1,5,6,2,3].  \nUsing Approach 1:\n  - Calculate the left boundaries: [null,null,1,2,1,4]\n  - Calculate the right boundaries and update maxArea:\n      [4,5,2,4,4,6] => Max Area = 10\n\n### Code for Approach 1:\n\n```java\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n         public int largestRectangleArea(int[] heights) {\n        Stack<Integer> st=new Stack<>();\n        int n=heights.length;\n        int left[]=new int[n];\n        int right[]=new int[n];\n        Arrays.fill(left,-1);\n        Arrays.fill(right,n);\n\n        int i=0,c=0;\n        while(i<n){\n            while(!st.isEmpty()&&heights[st.peek()]>=heights[i]){\n                st.pop();\n            }\n            if(!st.isEmpty()) left[i]=st.peek();\n            st.add(i);\n            i++;\n        }\n        st.clear();\n        i=n-1;\n        while(i>=0){\n            while(!st.isEmpty()&&heights[st.peek()]>=heights[i]){\n                st.pop();\n            }\n            if(!st.isEmpty()) right[i]=st.peek();\n            st.add(i);\n            c=Math.max(c,heights[i]*(right[i]-left[i]-1));\n            i--;\n        }\n        return c;\n    }\n}\n```\n## Approach 2\n\n### Intuition:\nSimilar to Approach 1, but with a slight optimization in how we handle the right boundaries.\n\n### Approach:\n1. Use a single pass:\n   - Traverse the histogram from left to right.\n   - For each bar, calculate its left boundary and simultaneously update the maximum area.\n   - When calculating the right boundary, instead of another pass, we calculate the width directly.\n2. To calculate the left boundary:\n   - Use a stack to store the indices of bars.\n   - Traverse the histogram from left to right.\n   - For each bar, pop elements from the stack until finding a smaller bar.\n   - The left boundary of the current bar is the index at the top of the stack.\n3. To calculate the width and update the maximum area:\n   - When calculating the right boundary, calculate the width directly using the current index and the index at the top of the stack.\n   - Update the maximum area by computing the area of the rectangle formed by each bar.\n\n### Explanation:  \n- Similar to Approach 1, but with a single pass and optimized calculation of the right boundary.\n\n### Time Complexity  \nO(n), where n is the number of bars in the histogram.\n\n### Space Complexity:\nO(n), used for the stack and left array.\n\n### Example with Clear Explanation:\nConsider the histogram [2,1,5,6,2,3].  \nUsing Approach 2:\n  - Calculate the left boundaries: [null,null,1,2,1,4]\n  - Calculate the right boundaries and update maxArea:\n      [null, 0, 1, 2, 1, 6] => Max Area = 10\n\n### Code for Approach 2:\n\n```java\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        Stack<Integer> st=new Stack<>();\n        int n=heights.length;\n        int left[]=new int[n];\n        Arrays.fill(left,-1);\n        int i=0,c=0;\n        while(i<n){\n            while(!st.isEmpty()&&heights[st.peek()]>=heights[i]){\n                int t=st.pop();\n                c=Math.max(c,heights[t]*(i-(!st.isEmpty()?st.peek():-1)-1));\n            }\n            if(!st.isEmpty()) left[i]=st.peek();\n            st.add(i);\n            i++;\n        }\n        while(!st.isEmpty()){\n            int t=st.pop();\n            c=Math.max(c,heights[t]*(n-(!st.isEmpty()?st.peek():-1)-1));\n        }\n        return c;\n    }\n}\n```\n![Please Upvote](https://codeforces.com/predownloaded/19/37/193730892e8675ebafc11519f6174bee5c4a5ab0.jpeg)\n
['Array', 'Stack', 'Monotonic Stack', 'Java']