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

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.

Largest Rectangle in Histogram ex1
fig-1
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.
Largest Rectangle in Histogram ex2
fig-2
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)