Largest Rectangle in Histogram

Difficulty: Hard · Topic: Stacks & queues

Given bar heights of a histogram (each bar width 1), return the area of the largest rectangle that fits entirely inside it. A monotonic stack finds, for every bar, how far left and right it can extend while staying the shortest — in O(n).

Examples

largest_rectangle([2,1,5,6,2,3])
→ 10

Bars 5 and 6 give 2 × 5 = 10.

largest_rectangle([2,4])
→ 4

Target complexity: time O(n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.