Largest Rectangle in Histogram - Easy Approach explained with images
Problem Statement Explained\n Describe your first thoughts on how to solve this problem. \nThis question wants to find the largest rectangle (ie largest area) t
# Problem Statement Explained\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis question wants to find the largest rectangle (ie largest area) that can be formed in the given histogram.\nWe are given an array of heights of the histogram bars and width of all is supposed to be 1 unit.\n\n---\n\n\n# Understanding \n<!-- Describe your approach to solving the problem. -->\nOk , so let\'s start by looking closely at this figure\n\n![histogram.jpg](https://assets.leetcode.com/users/images/1a982941-8afd-4dbe-a4e9-0517a46cf63c_1720892034.8849194.jpeg)\n\nThese numbers written in **blue** are indexes . We have to find the largest rectangle that can be formed using these bars. \nLet\'s start at index 0 , we have a bar of height 2 , this cannot alone make a rectangle ,right? So , we move on to the index 1 , and we get a bar of height 1 . Now look at the below image again.\n\n![histogram.jpg](https://assets.leetcode.com/users/images/dfcbade6-7699-470e-b4fd-05c5ad893ddd_1720892510.768726.jpeg)\n\nYou can easily see that the current bar we are at , ie of height 1 can form a rectangle with bar at index 0 which was height 2.\nSo , now let\'s calculate the width of this rectangle .\nWidth will be  `The current index we are on  - The index present in the stack -1` (Will be explaining this formula in code walkthrough section.)\n![histogram.jpg](https://assets.leetcode.com/users/images/7aea841f-b458-4104-888f-1053506661fc_1720893329.7742724.jpeg)\n\nThe red mark you see? that\'s the width of our new rectangle , since it is starting from 0 , we get our width as 1 directly without using the formula. The height will be 1 of course because that is the limiting height of the rectangle between the 0 th index bar and the 1st index bar. \n\nNow that we have both the height and the width , we can calculate the area of the rectangle.\n\nSuppose we are at index 4 and we are forming a rectangle with index 3 since it is longer. What will be the width then ? Let\'s see through an image again.\n\n![histogram.jpg](https://assets.leetcode.com/users/images/529b634b-508f-46e6-8c21-ef29877ff3d9_1720893884.6791706.jpeg)\n\nLook at the pink and purple lines . Our width of the rectangle will be this entire `Purple line - the Pink line`. Now , since currently we are not including bar at index 2 and ( height 5 )\n,` we will subtract 1 from it` . And that is how the width of your rectangle is going to be calculated .\n\n\n \n\n---\n# Code WalkThrough and Approach\n\nThe approach is going to be quite simple. We will just loop through the heights of the bars and the moment we get a height which is less than the one present in the stack , we realize that we can form a rectangle now.\n\nOkay, so we first start with the initializations. \n1. **n** : initialized to the length of the heights array.\n\n2. **maxArea** : initialized to 0 , this will hold the maximum area we get as we traverse through the bars.\n\n3. **stack** : A stack to hold the indices of the bars.\n\nNow , after initializing , we put a for loop which runs until i<=n .\n\n**Why =n ?**\n-> See , when we get heights that are greater than the ones that are in the stack , we push those heights inside the stack too. right.\n\nBut , what if when we reach the last height , we have heights left in the stack , that were never processed? How do we deal with them?\nThat\'s why we put a condition that : `int currHeight = (i==n) ? 0 : heights[i];` we process one extra artificial bar at i==n , and assume that it\'s height is 0 . So now what will happen is that this artificial height will be less than all the heights in the stack , so we keep popping and processing them , until the stack becomes empty.\n\nNow , look at this part of the code. \n```\n while(!stack.isEmpty() && currHeight<heights[stack.peek()])\n             {\n              \n                int top = stack.pop();\n             int width = stack.isEmpty() ? i: i-stack.peek()-1;\n              int area = heights[top]*width;\n            maxArea = Math.max(maxArea , area);\n\n                }//while\n```\n\nThis is the loop in which we traverse the array of heights until the stack is not empty , and the current height is less than the height in the stack (Why? Because ,when we encounter a height less than the previous one , we can form a rectangle from it)\n\n\n---\n\n\n# Code\n```java []\nimport java.util.Stack;\n\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        int n = heights.length;\n        int maxArea = 0;\n       Stack<Integer>stack = new Stack<>();\n     \n      for(int i=0;i<=n;i++)\n      {\n        int currHeight = (i==n) ? 0 : heights[i];\n\n        while(!stack.isEmpty() && currHeight<heights[stack.peek()])\n             {\n              \n                int top = stack.pop();\n             int width = stack.isEmpty() ? i: i-stack.peek()-1;\n              int area = heights[top]*width;\n            maxArea = Math.max(maxArea , area);\n\n                }//while\n\n           stack.push(i);\n\n         }//for loop\n       return maxArea;\n\n    }//function ends\n}//class end  \n```\n\n```python []\nclass Solution(object):\n    def largestRectangleArea(self, heights):\n        """\n        :type heights: List[int]\n        :rtype: int\n        """\n        n = len(heights)\n        max_area = 0\n        stack = []\n\n        for i in range(n + 1):\n            curr_height = 0 if i == n else heights[i]\n\n            while stack and curr_height < heights[stack[-1]]:\n                top = stack.pop()\n                width = i if not stack else i - stack[-1] - 1\n                area = heights[top] * width\n                max_area = max(max_area, area)\n\n            stack.append(i)\n\n        return max_area\n```\n          \n\n---\n# Complexity\n- Time complexity : $$O(n)$$\n<!-- Add your time complexity here, e.g.  --> \n\n- Space complexity : $$O(n)$$\n<!-- Add your space complexity here, e.g.  -->\n\n---\n**Feel free to ask any queries regarding this problem in the comments section**\n**Thankyou !**\n\n\n
['Array', 'Stack', 'Monotonic Stack', 'Python', 'Java']