Hard
Monotonic Stack
Largest Rectangle in Histogram
Each bar's widest rectangle spans until a shorter bar on either side.
Approach
Keep an increasing stack of bar indices. When a shorter bar arrives, pop taller bars and compute the area each can form, using the new index and the stack's next element as the width bounds. A sentinel zero at the end flushes the stack.
Time complexity
O(n)
Space complexity
O(n)
Common mistake
Getting the width wrong after a pop — it spans from the element now below on the stack (exclusive) to the current index (exclusive).
See it run, step by step
Generate an interactive lesson for Largest Rectangle in Histogram — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Largest Rectangle in Histogram