Maximum Area Rectangle in Histogram using linear search via stack of incomplete sub problems

We have already discussed lots of solution to solve this here, and using the stack to achieve is one of them.

Problem

Question: Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram.

(Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.)

Consider the histogram below:

Hieghts = { 6,2,5,4,5,1,6}

Max area of the rectangle:

Max area = 4 * 3 = 12



This problem seems like container-with-most-water problem discussed here. But the difference is that we are not using two "wood boards" to make a bucket, but using several boards with different heights.

Brute force solution

A straightforward answer is to go for each bar in the histogram and find the maximum possible area in histogram for it. Finally find the maximum of these values. This will require O(n^2) time but this will be huge if we have a big histogram with thousands of bars. 




Solution with Stack

Here we will use stack (of-course it rings the bell that recursive solution is also possible).

 Time complexity here will be O(n) as we will see. Though as discussed here, there are many better solutions available.

Here we process the elements from left to right order, and maintain a stack of information about started but yet unfinished histograms.The point of this algorithm is to maintain a stack where higher element is always greater or equal to the lower element. Why do we need to maintain that kind of stack? Because if we have a non-decreasing list, we can easily calculate the maximum area in one scan.

We just need to compare: height[i] * (n – i) for every i. (It will be clear in sometime).
So how do we maintain this stack? If we keep seeing larger element, we just need to push them onto the stack. If we see a smaller (compared to the top element on the stack) element, we need to do two things:

1. Pop the stack until we can maintain the non-decreasing order. Pushing the smaller element for m times, where m = number of popped elements.
2. Keep track of the maximum area that cause by those pop.

For example, we have height = {1,3,5,7,4}.
We push onto the stack for {1,3,5,7} then we see 4. 4 is less than 7, so we need to pop. We stop popping until we see 3. However many times we pop, we push 4 onto the stack. Therefore the resulted stack would be {1,3,4,4,4}. Because of popping 7, we need to remember that the maximum area that contains 7 is 7. The largest area that contains 5, the other element which get popped, is 10. So we take that down. We then finish processing all the elements in the original array and end up with a non-decreasing stack {1,3,4,4,4}. We can compute the largest area of this stack, which is 4*3 = 12. Since 12 is larger than the previous largest, 10, we output 12.

Code in java

public int largestRectangleArea(int[] height) {
    Stack<Integer> stack =
        new Stack<Integer>();
    int max = 0;
    int i = 0;
    while(i < height.length) {
        if(stack.isEmpty() ||
            height[i] >= stack.peek()) {
            stack.push(height[i]);
            i++;
        }
        else {
            int count = 0;
            while(!stack.isEmpty() &&
                stack.peek() > height[i]) {
                count++;
                int top = stack.pop();
                max = Math.max(max, top * count);
            }
            for(int j = 0; j < count + 1; ++j) {
                stack.push(height[i]);
            }
            i++;
        }
    }
     
    int count = 0;
    while(!stack.isEmpty()) {
        count++;
        max = Math.max(max, stack.pop() * count);
    }
    return max;
}

Dry running the code



Sources
http://tech-queries.blogspot.in/2011/03/maximum-area-rectangle-in-histogram.html
http://blog.theliuy.com/largest-rectangle-in-histogram/
http://tianrunhe.wordpress.com/2012/07/26/largest-rectangle-in-histogram/