Largest rectangle under a bar chart

Question

Given bar heights (for example depth at each price level of an order book), find the area of the largest rectangle that fits entirely under the bars.

heights = [2, 1, 5, 6, 2, 3]
-> 10          # the bars of height 5 and 6 span width 2: 5 x 2 = 10

Return the maximum rectangle area. The brute force over all (left, right) pairs is $O(n^2)$ ; aim for $O(n)$ .

Accepted Answer

For each bar, the widest rectangle of that bar's height reaches left until the first shorter bar and right until the first shorter bar. Keep a stack of indices with increasing heights. When a new bar is shorter than the stack top, that top has just met its right boundary, so pop it and settle its rectangle; the new left boundary is whatever now sits below it. When bar top is popped by a shorter bar at i, its rectangle spans from just after the previous shorter bar (left) to just before i, so width = i - left - 1 and area = heights[top] 	imes width. The trailing sentinel 0 forces every remain…

Largest rectangle under a bar chart

Your answer

More Coding questions