# Largest Rectangle in Histogram LeetCode Solution

Here, We see Largest Rectangle in Histogram LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

# List of all LeetCode Solution

## Problem Statement

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: (fig-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: (fig-2)
Input: heights = [2,4]
Output: 4```

## Largest Rectangle in Histogram Leetcode Solution C++

``````class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
int ans=0;
heights.push_back(0);
for(int i=0;i<heights.size();i++){
while(!st.empty() && heights[st.top()]>heights[i]){
int top=heights[st.top()];
st.pop();
int ran=st.empty()?-1:st.top();
ans=max(ans,top*(i-ran-1));
}
st.push(i);
}
return ans;
}
};
```Code language: C++ (cpp)```

## Largest Rectangle in Histogram Leetcode Solution Java

``````class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int[] lessFromLeft = new int[heights.length]; // idx of the first bar the left that is lower than current
int[] lessFromRight = new int[heights.length]; // idx of the first bar the right that is lower than current
lessFromRight[heights.length - 1] = heights.length;
lessFromLeft[0] = -1;

for (int i = 1; i < heights.length; i++) {
int p = i - 1;
while (p >= 0 && heights[p] >= heights[i]) {
p = lessFromLeft[p];
}
lessFromLeft[i] = p;
}
for (int i = heights.length - 2; i >= 0; i--) {
int p = i + 1;

while (p < heights.length && heights[p] >= heights[i]) {
p = lessFromRight[p];
}
lessFromRight[i] = p;
}
int maxArea = 0;
for (int i = 0; i < heights.length; i++) {
maxArea = Math.max(maxArea, heights[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
}
return maxArea;
}
}
```Code language: Java (java)```

## Largest Rectangle in Histogram Leetcode Solution JavaScript

``````var largestRectangleArea = function(heights) {
heights.push(0)
const stack = [];
let maxArea = 0, curr, currH, top, topH, area;

for(let i = 0; i < heights.length; i++) {
top = stack[stack.length-1];
topH = heights[top];
while(stack.length > 1 && topH > heights[i]) {
curr = stack.pop();
currH = heights[curr];
top = stack[stack.length-1];
topH = heights[top];
area = currH * (i - 1 - top);
maxArea = Math.max(area, maxArea);
}
if(stack.length && topH > heights[i]) {
curr = stack.pop();
currH = heights[curr];
area = currH * i;
maxArea = Math.max(area, maxArea);
}
stack.push(i);
}
return maxArea;
};
```Code language: JavaScript (javascript)```

## Largest Rectangle in Histogram Leetcode Solution Python

``````class Solution(object):
def largestRectangleArea(self, heights):
heights.append(0)
stack = [-1]
ans = 0
for i in xrange(len(heights)):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
ans = max(ans, h * w)
stack.append(i)
heights.pop()
return ans
```Code language: Python (python)```
Scroll to Top