Largest Rectangle in a Histogram

Given a histogram/bar graph, what is the largest rectangle (area) within?

histo-rect

This can be solved in O(n) using a simple stack algorithm.

The gist:
– Scan from left to right.
– Add to the stack when height is going up.
– Otherwise, this marks the end of a (previous) taller rectangle, which is checked for area.

References:
geeksforgeeks.com
Wikipedia

My implementation is in git and below:

Leave a Reply

Your email address will not be published. Required fields are marked *