# Leetcode Largest Rectangle in Histogram problem solution

Apr 25, 2023

In the Leetcode Largest Rectangle in Histogram problem solution 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

## Solution in C Programming

``````int largestRectangleArea(int* heights, int heightsSize){
int max=0;
for(int i=0; i<heightsSize; i++){
int volume=0;
// calculate the rect including each bar respectively
// forward and backward search
if(max/heightsSize>=heights[i]){
continue;
}
for(int j=i-1;j>=0;j--){
// backward search
if(heights[j]>=heights[i]){
volume+=heights[i];
}
else{
break;
}
}
for(int k=i;k<heightsSize;k++){
// forward search
if(heights[k]>=heights[i]){
volume+=heights[i];
}
else{
break;
}
}
if(volume>max){
// for the last rect
max = volume;
}
}
return max;
}``````

## Solution in C++ Programming

``````class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> left(heights.size(), 0);
vector<int> right(heights.size(), 0);
left[0] = -1;
for(int i=1;i<heights.size();i++){
int j = i-1;
while(j>=0 && heights[j]>=heights[i]){
j = left[j];
}
left[i] = j;
}
right[right.size()-1] = right.size();
for(int i=heights.size()-2;i>=0;i--){
int j = i+1;
while(j<right.size() && heights[j]>=heights[i]){
j = right[j];
}
right[i] = j;
}
int ans = 0;
for(int i=0;i<heights.size();i++){
ans = max(ans, (right[i]-left[i]-1)*heights[i]);
}
return ans;
}
};``````

## Solution in Java Programming

``````class Solution {
public int largestRectangleArea(int[] heights) {

if (heights.length == 0) {
return 0;
}

if (heights.length == 1) {
return heights[0];
}

int n = heights.length;
Stack<Integer> stack = new Stack<>();

int top;
int area;
int maxArea = -1;

int i = 0;

while (i < n) {

if (stack.empty() || heights[stack.peek()] <= heights[i]) {
stack.push(i++);
} else {
top = stack.pop();

if (stack.isEmpty()) {
area = heights[top] * i;
} else {
area = heights[top] * (i - stack.peek() - 1);
}

maxArea = Math.max(maxArea, area);
}
}

while (!stack.isEmpty()) {

top = stack.pop();

if (stack.isEmpty()) {
area = heights[top] * i;
} else {
area = heights[top] * (i - stack.peek() - 1);
}

maxArea = Math.max(maxArea, area);
}

return maxArea;
}
}``````

## Solution in Python Programming

``````class Solution:
def largestRectangleArea(self, heights):

heights.append(0)
n, maxi, stack = len(heights), 0, []

for i in range(n):
top = i
while len(stack) and heights[i] <= heights[stack[-1]]:
top = stack.pop()
maxi = max(maxi, heights[top]*(i-top))
heights[top] = heights[i]
stack.append(top)
return maxi``````

## Solution in C# Programming

``````// Divide and conquer solution ;
// Could be improved by building segment tree of Indexes of min values (Just for fun)
public class Solution

{
//        ||
//        ||
//  ||    ||    ||
//  || || || || ||    ||
//  || || || || || || ||
//  3  2  5  2  3  1  3
//     ^
//  Divide and conquer solution
//
// 1. select first min elemenent 3 [2] 5 2 3 1 ...
// 2. calculate max rectangle in:
// - left side [3]
// - right side [5 2 3 1 3]
// - count numbers from left to right, that larget than first min el [2]
//   and multiple on first min el, so count [3 2 5 2 3] = 6; 6 * 2 = 12
// 3. calc max

public int LargestRectangleArea(int[] heights)
{
return LargestRectangleArea(heights, 0, heights.Length);
}

private static int LargestRectangleArea(int[] heights, int from, int to)
{
if (from >= to)
return 0;

if (to - from == 1)
return heights[from];

int indexOfMinEl = GetMinElIndex(heights, from, to);

int rectangle = CalcRectangleFromFirstToLastEl(heights, indexOfMinEl);

// if siblings are similia, we are moving indexOfMinEl index
int begin = indexOfMinEl;
while (begin - 1 > -1 && heights[begin - 1] == heights[begin])
begin--;

// if siblings are similia, we are moving indexOfMinEl index
int end = indexOfMinEl;
while (end < heights.Length - 1 && heights[end] == heights[end + 1])
end++;

int rectLeft = LargestRectangleArea(heights, from, begin);
int rectRight = LargestRectangleArea(heights, end + 1, to);

int maxLeftRight = Math.Max(rectLeft, rectRight);

return Math.Max(rectangle, maxLeftRight);
}

public static int GetMinElIndex(int[] height, int from, int to)
{
int min = from;
for (int i = from; i < to; i++)
if (height[i] < height[min])
min = i;

return min;
}

private static int CalcRectangleFromFirstToLastEl(int[] height, int minIndex)
{
if (minIndex < 0)
return 0;

int sum = 0;
int i;

for (i = minIndex; i < height.Length; i++)
{
if (height[i] < height[minIndex])
break;

sum += height[minIndex];
}

for (i = minIndex - 1; i > -1; i--)
{
if (height[i] < height[minIndex])
break;

sum += height[minIndex];
}

return sum;
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.