Largest rectangle in histogram

Given the heights of bars of width 1, return the area of the largest rectangle that fits under the histogram.

Before you code

Every candidate rectangle has some bar as its shortest. For bar i, the widest rectangle of height heights[i] extends left to just after the previous shorter bar and right to just before the next shorter bar. So you need both neighbors for every bar.

Hints

1. Keep a stack of indexes with increasing heights.
2. When a bar shorter than the top arrives, pop the top: the new bar is its next smaller, and the index now on top of the stack is its previous smaller.
3. Its width is i - stack[-1] - 1 (or i if the stack is empty); compute the area.
4. Append a height of 0 at the end so that every bar is eventually popped and measured.

Production & complexity notes

When solving Largest rectangle in histogram on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Deques and monotonic stacks to reinforce the underlying pattern.

What it practices

Reading both neighbors from one monotonic stack, from Deques and monotonic stacks.