Largest Rectangle in Histogram LeetCode Solution

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

Largest Rectangle in Histogram 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

• C++ Solution
• Java Solution
• JavaScript Solution
• Python Solution

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)