Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Solution:

What's the maximum area one can obtain that has to include a certain bar?

Let's say we want to solve this for bar i with height[i], The area would include the following. * The bar itself * All the bars on the left and right side where this bar has the minimum height.

We maintain two arrays where left and right. Each array represents the number of bars on the side where this bar has minimum heights. And then we calculate area including each bar and take the maximum of that. Bar area of index i is height[i] * (left[i]+ right[i] + 1)

class Solution {
public int largestRectangleArea(int[] heights) {        
        int n = heights.length;
        if(n == 0) {
            return 0;
        }
        int max = 0;
        int[] left = new int[n];
        int[] right = new int[n];
        
        left[0] = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i=1;i<n;i++) {
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            if(stack.isEmpty()) {
                left[i] = i;
            }else {
                left[i] = i - stack.peek() - 1;
            }
            stack.push(i); 
            
        }
        
        right[n-1] = 0;
        stack.clear();
        stack.push(n-1);
        for(int i=n-2;i>=0;i--) {
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            if(stack.isEmpty()) {
                right[i] = n - 1 - i;
            }else {
                right[i] = stack.peek() - i - 1;
            }
            stack.push(i);
        }
        for(int i=0;i<n;i++) {
            int area = (left[i] + right[i] + 1) * heights[i];
            max = Math.max(max, area);
        }
        return max;
    }
}