Friday, July 5, 2013

Largest area in a Histogram

Find the maximum area of a rectangle that fits entirely in the Histogram.

For e.g in the below histogram the maximum area of the rectangle is 2 * 80  = 160

The length of each bar will be the input, and the width of each bar is same, 1
The naive approach can be to select one histogram at a time, find the maximum area which can be formed with this, finally return the maximum value over all the histogram.
Time Complexity O(n^2), Space Complexity O(1)
Can we do better. Lets have a look if we are computing some of the results over and over or if any of the computations are unnecessary.