leetExpert
Practice

Largest Rectangle in Histogram

Module 8 · Stacks

Problem

Given bar heights in a histogram (all width 1), return the area of the largest rectangle that fits entirely inside it.

Examples

Example 1

Input[2,1,5,6,2,3]Output10

Explanation. height 5 × width 2, over bars 5 and 6

Example 2

Input[2,4]Output4

Example 3

Input[3,3,3]Output9

Explanation. height 3 × width 3

Constraints

1 ≤ n ≤ 10⁵ · heights in [0, 10⁴].

Attempt it first

This is the module capstone and a genuinely hard problem — expect to spend real time. Don't reach for the stack immediately; first find the O(n²) structural insight (Hint 1), which is 80% of the solution. The stack is "merely" how that insight gets computed in one pass.