Largest Rectangle in Histogram (Stack)
A hard Stack problem included in Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Stack
- Sheets
- 2
- Core for
- 8 roles
- Platform
- LeetCode
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 = [2,1,5,6,2,3]
- Output
- 10
- Why
- The largest rectangle spans bars at indices 2 and 3 with heights 5 and 6, giving width 2 and height 5, for area 10.
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-09Every 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.
What each operation costs
| Operation | Time |
|---|---|
| push item onto the top | O(1) |
| pop item from the top | O(1) |
| inspect the topmost element | O(1) |
What usually goes wrong with Stack
- Popping from or peeking into an empty stack without first verifying that the size is positive, causing runtime null pointer or empty collection errors.
- Forgetting to verify that the stack is completely empty at the end of bracket matching, which mistakenly accepts strings with dangling unclosed opening symbols.
- Storing values instead of indices in monotonic stacks, making it impossible to calculate distance intervals between matching elements afterwards.
Which roles need this problem
Stack is a core topic for these 8 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 9 more roles, including Frontend Engineer, Data Engineer, Game Developer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Stack problems
Problem set and role mapping as of .