# Largest Rectangle in Histogram Leetcode Solution

In this post, we are going to solve the Largest Rectangle in Histogram Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

## Problem

Given an array of integers `heights` representing the histograms 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`

Now, lets see the leetcode solution of Largest Rectangle in Histogram Leetcode Solution.

### Largest Rectangle in HistogramLeetcode Solution in Python

```class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
ans = 0
stack = []

for i in range(len(heights) + 1):
while stack and (i == len(heights) or heights[stack[-1]] > heights[i]):
h = heights[stack.pop()]
w = i - stack[-1] - 1 if stack else i
ans = max(ans, h * w)
stack.append(i)

return ans
```

### Largest Rectangle in Histogram Leetcode Solutionin CPP

```class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
stack<int> stack;

for (int i = 0; i <= heights.size(); ++i) {
while (!stack.empty() &&
(i == heights.size() || heights[stack.top()] > heights[i])) {
const int h = heights[stack.top()];
stack.pop();
const int w = stack.empty() ? i : i - stack.top() - 1;
ans = max(ans, h * w);
}
stack.push(i);
}

return ans;
}
};
```

### Largest Rectangle in Histogram Leetcode Solution in Java

```class Solution {
public int largestRectangleArea(int[] heights) {
int ans = 0;
Deque<Integer> stack = new ArrayDeque<>();

for (int i = 0; i <= heights.length; ++i) {
while (!stack.isEmpty() && (i == heights.length || heights[stack.peek()] > heights[i])) {
final int h = heights[stack.pop()];
final int w = stack.isEmpty() ? i : i - stack.peek() - 1;
ans = Math.max(ans, h * w);
}
stack.push(i);
}

return ans;
}
}
```

Note: This problem Largest Rectangle in Histogram is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

Sharing Is Caring