Last updated on January 29th, 2025 at 02:26 am

Here, we see the Largest Rectangle in Histogram LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Stack

Level of Question

Hard

Largest Rectangle in Histogram LeetCode Solution

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Monotonic Stack”. This pattern involves using a stack to maintain a sequence of elements in a specific order (in this case, a non-decreasing order of heights). The stack is used to efficiently calculate the largest rectangle in a histogram by processing each bar and determining the maximum area that can be formed with it as the smallest height.

3. Code Implementation in Different Languages

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

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

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

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

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)

• The code uses the Monotonic Stack pattern to efficiently calculate the largest rectangle area in a histogram.
• The time complexity is O(n) because each bar is processed at most twice (once pushed and once popped), and the space complexity is O(n) due to the stack.