Problem of the day: Largest rectangle in a histogram

Problem of the day for today is Largest rectangle in a histogram: Given n non-negative integers representing the histogram’s bar heights where the width of each bar is 1, find the area of largest rectangle in the histogram.

largest-rectangle-in-histogram

In this example, we are given 7 heights [6, 2, 5, 4, 5, 1, 6] and can see that the area of the largest rectangle is 3*4 = 12.

Continue reading