Largest Rectangle in Histogram : #84

Imagine you are planning to build a residency in an area.

You can create building of different heights or houses. As it is a residency all the buildings have to be near each other.

If there is not enough space to its adjacent neighbour the building cannot expand.

For example If there is a river/smaller building in between you cannot expand beyond that.

As we have a constraint budget and we want to maximise the area of your buildings.

We will have to consider different building heights and check how far it can expand until we find a height which gives maximum area.

When can a building expand?

Only when its adjacent buildings are either equal to or greater than it’s own height.

Hence we need to keep on popping adjacent buildings in both sides which has a height greater than the current height.

Expand to its left:

Expand to its right:

Calculate Width:

Area = Height * width

So overall we did 4 steps -

• Calculate how far a building can expand to its left
• Calculate how far a building can expand to its right
• Calculate the width by combining left and right widths.
• Multiply its height to the area.

github.com/tanu02/LeetCode/blob/master/Stack/src/LargestRectangleInHistogram.java