Largest Rectangle in Histogram

You are given an array heights where heights[i] is the height of the i-th bar in a histogram. Every bar has width 1 and the bars sit side by side.

Find the area of the largest rectangle that fits entirely inside the histogram. The rectangle can span any range of consecutive bars, and its height is limited by the shortest bar in that range.

For any bar, the widget shades the widest rectangle capped at that bar's height — the answer is the largest such rectangle over the whole histogram.

Try it yourself