# LeetCode 84. Largest Rectangle in Histogram

## Description

https://leetcode.com/problems/largest-rectangle-in-histogram/

Given an array of integers `heights` representing the histogram’s bar height where the width of each bar is `1`, return the area of the largest rectangle in the histogram.

Example 1:

```Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
```

Example 2:

```Input: heights = [2,4]
Output: 4
```

Constraints:

• `1 <= heights.length <= 105`
• `0 <= heights[i] <= 104`

## Java Solution

``````class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}

int maxArea = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);

for (int i = 0; i < heights.length; i++) {
int currentBarHeight = heights[i];

while (stack.peek() != -1 && currentBarHeight <= heights[stack.peek()]) {
int height = heights[stack.pop()];
int width = i - stack.peek() - 1;

int area = height * width;
maxArea = Math.max(area, maxArea);
}

stack.push(i);
}

while (stack.peek() != -1) {
int height = heights[stack.pop()];
int width = heights.length - stack.peek() - 1;

int area = height * width;
maxArea = Math.max(area, maxArea);
}

return maxArea;

// Time complexity : O(n). n numbers are pushed and popped.
// Space complexity : O(n). Stack is used.
}
}``````

## Python Solution

``````class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
if not heights:
return 0

max_area = 0

stack = []
stack.append(-1)

for i in range(len(heights)):
current_height = heights[i]

while stack[-1] != -1 and current_height < heights[stack[-1]]:
height = heights[stack.pop()]
width = i - stack[-1] - 1

area = height * width

max_area = max(area, max_area)

stack.append(i)

while stack[-1] != -1:
height = heights[stack.pop()];
width = len(heights) - stack[-1] - 1

area = height * width
max_area = max(area, max_area)

return max_area
``````
• Time Complexity: O(N)
• Space Complexity: O(N)