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

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

Approach:

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.