Largest Rectangle in Histogram — Step-by-Step Visualization

Algorithm Pattern

Monotonic Stack (Increasing)

Key Idea

We maintain a stack of bars in increasing height order. When we find a bar shorter than the stack top, we KNOW the taller bar can't extend further right. We pop it and compute the area it can form leftward. The 'start' index stored with each bar represents how far left a rectangle of that height can extend.

Step-by-Step Approach

1. Initialize an empty stack. Each entry stores (start_index, height).
2. Iterate through each bar with index `i`.
3. Track a `start` pointer — how far left the current bar's rectangle can extend.
4. While the stack is non-empty AND the current bar's height < stack top's height: pop the top, compute its area (height × (i - start)), update maxArea.
5. Push the current bar with its effective `start` onto the stack.
6. After the loop, process remaining bars: each extends to the end of the array.

Common Gotchas

• When popping a bar, its rectangle extends from its stored `start` to the current index `i` — not from where it was pushed.
• Don't forget to drain the remaining stack at the end. Each leftover bar's width = n - start.