# Largest Rectangle In Histogram Problem Solution

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.

```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.```

Table of Contents

## Problem Solution In Python

``````class Solution:
def largestRectangleArea(self, arr: List[int]) -> int:
stack,pos,maxA=[],0,0
n=len(arr)
for i in range(n):

while(stack and arr[stack[-1]]>arr[i]):
pos= stack.pop()
if stack:
area=arr[pos]*(i-stack[-1]-1)
maxA=max(maxA,area)
else:
area=arr[pos]*(i-0)
maxA=max(maxA,area)

stack.append(i)

while stack:

pos= stack.pop()
if stack:
area=arr[pos]*(n-stack[-1]-1)
maxA=max(maxA,area)
else:
area=arr[pos]*(n-0)
maxA=max(maxA,area)

return maxA
``````

## Problem Solution In Java

``````class Solution {
public int largestRectangleArea(int[] heights) {
Stack < Integer > stack = new Stack < > ();
int[] left = new int[heights.length];
int[] right = new int[heights.length];
Arrays.fill(right,heights.length);
Arrays.fill(left,-1);
for(int i = 0;i<heights.length;i++){
while(!stack.empty()&&heights[stack.peek()]>heights[i]){
right[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}

stack = new Stack<>();
for(int i = heights.length-1;i>=0;i--){
while(!stack.empty()&&heights[stack.peek()]>heights[i]){
left[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}

int maxArea = 0;
for (int i = 0; i < heights.length; ++i) {
maxArea = Math.max(maxArea,(right[i]-left[i]-1)*heights[i]);
}

return maxArea;
}
}
``````

## Problem Solution In C++

``````int largestRectangleArea(vector<int>& arr) {
int n=arr.size();
if(n==0) return 0;
stack<int> s;
int i=0,area=INT_MIN;
while(i<n)
{
if(s.empty()||arr[s.top()]<=arr[i])
{
s.push(i);i++;
}
else
{
int num=s.top();s.pop();
int l=s.empty()?-1:s.top();
area=max(area,arr[num]*(i-l-1));
}
}
while(!s.empty())
{
int num=s.top();s.pop();
int l=s.empty()?-1:s.top();
area=max(area,arr[num]*(i-l-1));
}
return area;
}
``````

## Problem Solution In C

``````struct tagStackObj{
int height;
int width;
};

int largestRectangleArea(int* heights, int heightsSize){
int maxSize = 0;
int squareSize = 0;
int i;
int *p = heights;
int index = 0;
int stride = 0;
struct tagStackObj *pStack = NULL;

if (0 == heightsSize)
return 0;

pStack = malloc(heightsSize * sizeof(struct tagStackObj));
pStack[index].width = 1;
pStack[index].height = heights[0];

for (i = 1; i < heightsSize; i++){
if (p[i] >= pStack[index].height){
index++;
pStack[index].height = p[i];
pStack[index].width = 1;
}
else{
stride = 0;
while ((index >= 0) && (pStack[index].height > p[i])){
stride += pStack[index].width;
squareSize = stride * pStack[index].height;
maxSize = squareSize > maxSize ? squareSize : maxSize;
index--;
}

pStack[++index].height = p[i];
pStack[index].width = stride + 1;
}
}

stride = 0;
while ((index >= 0) && (pStack[index].height > -1)){
stride += pStack[index].width;
squareSize = stride * pStack[index].height;
maxSize = squareSize > maxSize ? squareSize : maxSize;
index--;
}

return maxSize;
}
``````

If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.