Histograms and Stacks

Largest Area Rectangle in a Histogram

Question: Find the rectangle with largest area that can be enclosed by a given histogram.

This is a very well known coding interview question and a personal favorite of mine. There are few clever ways of solving it. I am writing this post to specifically illustrate the thought process behind solving the problem using stacks. But I’ll skim through other ways too. Let’s begin.

Method 1 - Naive Solution: If n is the number of bars in the histogram, one can always compute the maximum area rectangle starting at the i-th bar (i.e. whose left edge is the i-th bar). Each such computation takes O(n) time, and the overall solution takes O(n²) time.

Can we do something better? Of course we can!

Method 2 - Divide and Conquer: An O(n log n) solution is also possible by using a divide and conquer approach.

Hint: Divide the histogram into two equal parts. The largest rectangle can be either be (1) completely in the left half, (2) completely in the right half, or (3) include the middle and extend into both sides. Then, one can recurse on (1) and (2) and solve (3), an easier problem than the original one which can be solved in O(n) time.

Another variation of the divide and conquer method divides the rectangle in a smarter way. A detailed description of this approach is given in my favorite coding problems website geeksforgeeks.

There is an even faster way of solving this problem, and it involves using stacks.

Method 3 - The Stacks Solution: Let’s first start with identifying all feasible solutions to the problem using our illustration.

Here the lengths of the lines indicates the widths of rectangles, and the numbers indicate corresponding heights. Its immediately clear that the lengths of the feasible solutions have a nested structure. The nested structures should be followed by a voice in mind which says STACKS!

So we will be storing the histogram heights in our stack. As we parse through the histogram heights, we will store on our stack the heights of all rectangles which can be extended further to the right. When popping something off of the stack (because rectangle of that height can’t extend any further to the right) we will need to know its starting location to compute total area of this rectangle. For this reason, we will store the indices of the heights along with the heights.

Here is the complete code in Python:

Its clear that our stack will contain strictly increasing sequence of heights at all times. Padding the heights with 0 on both sides will make sure that when in the end, the 0 on the right is compared to things on top of the stack, everything on the stack will be popped off (since it is greater than 0) till we reach the 0 on the left (which is at the bottom of the stack). At this point, all rectangles are closed off, and the function returns max_area.

The end.