Largest Rectangle in Histogram (Stack)
A hard Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 2
- Core for
- 9 roles
The problem
Given an array of integers representing the heights of bars in a histogram where each bar has width 1, find the area of the largest rectangle that can be formed within the histogram.
Example 1
- Input
- heights = [3,2,5,4,6,1]
- Output
- 12
- Why
- Bars at indices 1-3 with heights 2,5,4 form rectangle of height 2 and width 3, area 6; bars at indices 2-4 with heights 5,4,6 form height 4 width 3 area 12.
Example 2
- Input
- heights = [2,4]
- Output
- 4
- Why
- The rectangle using the second bar alone gives area 4.
Constraints
- 1 <= heights.length <= 10^5
- 0 <= heights[i] <= 10^4
How to think about it
Updated 2026-09-29Every candidate maximal rectangle is bottlenecked by at least one bar whose full height it uses. The question reduces to: for each bar i, how far can its height extend left and right before hitting a bar strictly shorter? That is the classic nearest smaller element query on both sides, and a monotonic stack resolves both boundaries cleanly.
Approaches, worst first
Expand around each bar
time O(n^2) · space O(1)
For every bar i, walk left until seeing a bar shorter than heights[i], walk right similarly, and compute `heights[i] * width`. Correct and straightforward, but degrades to quadratic time on uniform or monotonically sorted histograms.
Separate left and right smaller bounds
time O(n) · space O(n)
Precompute two arrays `leftSmaller` and `rightSmaller` using two monotonic stack passes. Then iterate once over all bars, evaluating `heights[i] * (rightSmaller[i] - leftSmaller[i] - 1)`. Takes three clean passes and uses linear auxiliary storage.
Single-pass monotonic increasing stackWrite this one
time O(n) · space O(n)
Maintain an increasing stack of indices. When encountering a bar shorter than the stack top, pop the top: the popped bar's right boundary is the current index, and its left boundary is the new stack top index. Append a zero height sentinel at the end to flush all remaining bars.
Where people lose marks · 3
- Width calculation off-by-one: when the stack becomes empty after popping, the popped bar was the shortest seen so far, meaning its rectangle extends all the way back to index 0, so the width is `i`, not `i - 1`.
- Omitting a final flush or sentinel leaves bars on the stack when the histogram ends, missing rectangles supported by tall bars at the right edge.
- Zero height bars produce 0 area and must not cause division or empty boundary crashes.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .