Working Java Program For Largest Rectangle in Histogram

Here we will try to find a solution for largest rectangle in histogram problem. We will use “LeetCode 84. Largest Rectangle in Histogram” problem as an example here. It says:

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.

We have above histogram as input. I have highlighted largest rectangle area below.

I am not going to discuss brute-force method here. We will try to find a solution in optimal time complexity. Optimal time complexity can’t be less than O(n) as we would have to traverse all the bars in the histogram at least once to find the maximum rectangle area.

So how do we find maximum rectangle area in a histogram? We can do one thing. We will loop through the bars one by one & for each bar we will find the maximum rectangular area where current bar is the smallest one. Then from all the rectangle areas calculated, we will take the maximum one. Now how do we find the maximum rectangular area where a particular bar is the smallest one? We will move left side one by one & increment count till we find a bar whose value is less than the selected bar value. Same goes for the right side. We will increment the count till we find a right side bar whose value is less than the selected bar value. These are the left boundary & the right boundary of the rectangular area. We will multiply the bar count within the boundary with the selected bar value. That is the maximum rectangle area where the selected bar is the smallest one. You can see the diagram above which shows maximum rectangle area when we consider each bar separately.

How do we implement this logic in code? Which data structure should be optimal to find the left boundary & the right boundary of the maximum rectangular area for current bar? Here stack comes into the picture. We will start pushing the index of the bars in the stack when value is in ascending order (new bar value is greater than current stack top bar value). Once we encounter a new value which is less than current stack top bar value, we know we have found right boundary for the stack top. As we are pushing bar index when bar value is in ascending order, left boundary of the stack top is the adjacent element which is right below the current stack top. So we can easily calculate the maximum rectangle area for the bar whose index is currently sitting at the stack top.
Each element is pushed & popped only once in the stack. As we traverse all elements in the histogram, time complexity of the above problem would be O(n) which is linear.

Here is a complete Java code solution of this LeetCode problem using stack based approach discussed above.

class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        //stack keeping index of elements in ascending order
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0;
        for(; i < heights.length;){
            if(stack.isEmpty() || heights[stack.peek()] <= heights[i]){
                stack.push(i);
                i++;
            } else {
                int currentIndex = stack.pop();
                //left border of a element is the previous index with lower value
                int leftBorder = stack.isEmpty() ? -1 : stack.peek();
                int area = heights[currentIndex] * (i - leftBorder - 1);
                if(maxArea < area){
                    maxArea = area;
                }
            }
        }
        while(!stack.isEmpty()){
            int currentIndex = stack.pop();
            int leftBorder = stack.isEmpty() ? -1 : stack.peek();
            int area = heights[currentIndex] * (i - leftBorder - 1);
            if(maxArea < area){
                maxArea = area;
            }
        }
        return maxArea;
    }
}