hardCodingConceptMidSenior
Find the largest rectangle in a histogram in linear time, and tell me what the stack holds at every step.
Keep a stack of bar indices with strictly increasing heights. When a bar no taller than the top arrives, pop: the popped bar's rectangle runs from just after the new top to just before the current bar. A height-zero sentinel flushes the stack. Each index is pushed once and popped at most once, so it is O(n).
5 min readUpdated 2026-10-09Target archetype: Big Tech, Enterprise Captive, Product Startup
Answer
Short answer
Use a monotonic stack of bar indices whose heights strictly increase from bottom to top. When a bar arrives that is no taller than the top, pop the top. Its rectangle runs from just after the new top to just before the arriving bar. A sentinel bar of height zero at the end flushes whatever is left. Every index is pushed once and popped at most once, so the largest rectangle takes O(n) time and O(n) space.
Was this answer helpful?
Likely follow-ups
- Find the largest rectangle of 1s in a binary matrix. How does the histogram scan become the inner loop?
- Write the two-pass version with previous-smaller and next-smaller arrays. What does it make easier to explain?
- Return the boundaries of the best rectangle, not just its area. What extra state do you keep on pop?
- Why does splitting the histogram at its minimum bar degrade to quadratic time on sorted input?
Related questions
- For each element of an array, find the first element to its right that is larger. State the invariant your stack maintains.mediumAlso on monotonic-stack and stacks4 min
- Return the maximum of every window of size k as it slides across the array. Why a deque, and what is the invariant?hardAlso on amortised-analysis and arrays5 min
- Implement a FIFO queue using only two stacks, then tell me what a dequeue costs.mediumAlso on stacks and amortised-analysis4 min
- Appending to a dynamic array is O(1) amortised. Derive that, then defend it against someone who points out that a single append copies the whole array.mediumAlso on amortised-analysis5 min