Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Each bar is the height of some rectangle; the question is how far left and right that height can extend before it hits a shorter bar. Brute force checks every bar's reach by scanning outward, O(n²). The optimal answer keeps a monotonic increasing stack of bar indices: when a bar shorter than the stack top arrives, the top bar can't extend any further right, so you pop it and finalise its rectangle. Each bar is pushed and popped once — O(n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you see that each bar's maximal rectangle is bounded by the nearest shorter bar on each side, and whether you can compute both boundaries in a single monotonic-stack pass instead of two outward scans.
Where candidates slip
Storing heights instead of indices (so width can't be computed), or mishandling the width as i - top - 1 after popping, especially the empty-stack case where the bar reaches the far left.
How to stand out
Explain the invariant: the stack holds bars in increasing height, so when you pop, the new top is exactly the nearest shorter bar on the left and the current index is the nearest shorter (or equal) bar on the right. Mention the sentinel that flushes the stack.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewNew bar at index i, height hStack top bar >= h?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Expand Each Bar Outward
1Hint 1Explore hintHide hint
Make each bar the limiting height. How wide can a rectangle of that exact height be? It stops the moment a shorter bar appears on either side.
2Hint 2Explore hintHide hint
For each index i, walk left while bars are >= heights[i], walk right while bars are >= heights[i]. The width is right - left + 1.
3Hint 3Explore hintHide hint
area = heights[i] × width. Take the max over all i. Two outward scans per bar is the O(n²) cost.
A · Core idea
Treat every bar as the shortest bar of some candidate rectangle. The rectangle's height is then fixed at heights[i], and its width is however far that height can stretch in both directions before hitting a strictly shorter bar.
Why fix the shortest bar. Any rectangle has a single limiting height — its shortest bar. If you enumerate over 'which bar is the limiter', you cover every possible rectangle exactly once. So for bar i, expand left and right while neighbouring bars are at least heights[i]; the moment you hit something shorter, that side's wall is set.
Computing the width. Let left be the first index going left that is shorter than heights[i], and right the first going right that is shorter. The rectangle spans right - left - 1 bars, all at least heights[i] tall, so its area is heights[i] × (right - left - 1).
Why it's slow and where it repeats work. A nearly-sorted-ascending histogram like [1,2,3,...,n] makes each bar scan all the way to one end, so the outward walks cost O(n) each and the total is quadratic. Crucially, those scans recompute the same boundaries over and over — the bar to your left already knew where the next shorter bar was. A stack lets you remember that instead of rescanning, which is the leap to the linear solution.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
heights = [2, 1, 5, 6, 2, 3]Array state
start at i=2
height 5, left=right=2
max area = 10C · Code with teaching comments
Reference implementation previewpublic class Solution { public static long largestRectangle(int[] heights) { int n = heights.length; long best = 0; for (int i = 0; i < n; i++) {Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Every rectangle is uniquely identified by its shortest bar, so iterating over 'which bar is the limiter' is complete. The inefficiency is rediscovering each bar's left/right shorter-neighbour from scratch — exactly the boundaries a monotonic stack computes once.
ComplexityO(n²) time, O(1) space — For each of the n bars you may scan up to n-1 bars to the left and right to find where the height can no longer extend. That's O(n) work per bar, O(n²) overall. No extra data structures, so O(1) space.
E · Edge cases and pitfalls3Multiplying int width by int height without casting to long — overflow on large inputs.Explore edge casesHide edge cases
Pitfalls
- Multiplying int width by int height without casting to long — overflow on large inputs.
- Using > instead of >= and double-counting or missing equal-height runs.
- Believing the outward scans are cheap — they are O(n) each on a monotone histogram.
Approach 2 of 2 · Optimal
Monotonic Increasing Stack (Optimal)
1Hint 1Explore hintHide hint
When you're standing on bar i, which earlier bars still have an 'open' rectangle that could extend to i? Only those shorter than or equal to bar i — the taller ones were already cut off.
2Hint 2Explore hintHide hint
Keep a stack of indices whose heights are non-decreasing. When a new bar is shorter than the top, the top bar can't extend past i, so finalise it: pop, its right wall is i and its left wall is the new top.
3Hint 3Explore hintHide hint
Width after popping index t is i - stack.top - 1, or i if the stack is now empty. Append a virtual 0 at the end so every leftover bar gets popped and measured.
A · Core idea
Maintain a stack of bar indices whose heights are non-decreasing from bottom to top. Walk left to right; at each new bar (and one final virtual bar of height 0), pop every stacked bar that is at least as tall as the current one, finalising its rectangle as you pop.
The invariant and why it's everything. The stack is always non-decreasing in height. So for any bar still on the stack, every bar below it is shorter — meaning the bar directly below is its nearest shorter bar on the left. When a new bar at index i is shorter than the top, that top bar has just met its nearest shorter bar on the right: index i. Both walls are now known in O(1), which is exactly what the brute force re-scanned for.
Computing the width on pop. Pop the top index t with height heights[t]. Its right wall is i (the bar that triggered the pop). Its left wall is whatever is now on top of the stack — the nearest shorter bar to the left — at index newTop. The rectangle spans the bars strictly between those walls: width i - newTop - 1. If the stack is empty after popping, no shorter bar exists to the left, so the bar reaches the far-left edge and width is just i.
Why pop on `>=` and not only `>`. Popping when the top is equal in height as well keeps the measurement clean: an equal bar's rectangle will be re-discovered from the surviving bar of the same height, so no area is lost, and you avoid leaving stale equal bars that complicate the width math. Either a strict or non-strict convention works as long as it's consistent; >= is the simplest to reason about.
The sentinel that flushes the stack. After the last real bar, bars that never met a shorter neighbour on the right are still on the stack. Processing one extra index i = n with height 0 (shorter than everything) forces every remaining bar to pop and be measured, with right wall n. That's why the loop runs to i == n.
Why it's O(n). Push happens once per index. A pop also happens at most once per index — once finalised, a bar never returns. So across the entire pass there are at most n pushes and n pops; the inner while is amortised O(1). Linear time, with the stack as the only extra memory.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
heights = [2, 1, 5, 6, 2, 3]Array state
before i=4
stack holds indices 1,2,3 (heights 1,5,6)
10C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The stack turns 'find the nearest shorter bar on each side' — two outward scans in the brute force — into a single forward pass. The reusable idea: a monotonic stack remembers candidates whose answer isn't decided yet and resolves each the instant its boundary appears. The same engine solves Next Greater Element, Trapping Rain Water, and Maximal Rectangle (run this per matrix row).
ComplexityO(n) time, O(n) space — Each index is pushed exactly once and popped at most once. All other work per step is O(1). With at most n pushes and n pops over the whole run, the total is O(n) time. The stack holds at most n indices, so O(n) space.
E · Edge cases and pitfalls8heights = [5] — Pushed at i=0; sentinel at i=1 pops it with width 1 → area 5.Explore edge casesHide edge cases
Edge cases handled
heights = [5]Pushed at i=0; sentinel at i=1 pops it with width 1 → area 5.heights = [1, 1, 1, 1]All equal; popping on >= merges them so the sentinel finalises a width-4 rectangle → area 4.heights = [0, 0]Every bar is height 0; all areas are 0, answer 0.strictly increasing [1,2,3,4]Nothing pops until the sentinel, which then pops all four, giving max area 4 (the bar 4 alone vs 1×4).
Pitfalls
- Pushing heights instead of indices — you lose the ability to compute width.
- Forgetting the trailing sentinel, leaving the tallest bars unmeasured.
- Getting the width wrong when the stack empties — it should be i, not i - 1.
- Using int for the area accumulator and overflowing.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewimport java.util.*; public class Solution { public static long largestRectangle(int[] heights) { int n = heights.length;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Pushing heights instead of indices
Width depends on positions: i - newTop - 1. With only heights on the stack you can't recover the left boundary's index, so you can't compute width at all.
Explore the code comparisonHide the code comparison
Pushing heights instead of indices
Width depends on positions: i - newTop - 1. With only heights on the stack you can't recover the left boundary's index, so you can't compute width at all.
Don't write this
stack.push(heights[i]); // height only
// ... no way to know where this bar startedWrite this instead
stack.push(i); // index — heights[i] is still reachable2Missing the flush sentinel
Bars that never meet a shorter bar on their right stay on the stack forever. Without a final height-0 pass, their rectangles — often the largest — are never measured.
Explore the code comparisonHide the code comparison
Missing the flush sentinel
Bars that never meet a shorter bar on their right stay on the stack forever. Without a final height-0 pass, their rectangles — often the largest — are never measured.
Don't write this
for i in range(n): # stops at the last real bar
...
stack.append(i)
return best # leftover bars never poppedWrite this instead
for i in range(n + 1): # one extra virtual bar
h = 0 if i == n else heights[i]
... # flushes everything3Width math after an empty pop
When the stack becomes empty after popping, the bar extends to the far left, so its width is i (positions 0..i-1), not i - 1.
Explore the code comparisonHide the code comparison
Width math after an empty pop
When the stack becomes empty after popping, the bar extends to the far left, so its width is i (positions 0..i-1), not i - 1.
Don't write this
int width = i - stack.peek() - 1; // crashes / wrong when emptyWrite this instead
int width = stack.isEmpty() ? i : i - stack.peek() - 1;Revise
Carry the pattern into the interview
Pattern to remember
Monotonic increasing stack of indices; pop finalises a rectangle
Code pattern to memorize
for i in 0..n: # i == n acts as a height-0 sentinel
h = (i < n) ? heights[i] : 0
while stack not empty and heights[stack.top] >= h:
height = heights[stack.pop()]
width = stack.empty() ? i : i - stack.top - 1
best = max(best, height * width)
stack.push(i)Rules to remember
- 1Push indices, not heights — you need the index to compute width as
i - newTop - 1. - 2When you pop bar
h, its right boundary is the current indexiand its left boundary is the new stack top after popping. - 3Width is
i - stack.top - 1after popping; if the stack is empty,hextends all the way left, so width isi. - 4Append a virtual 0-height bar at the end (or loop to
i == n) to flush every remaining bar off the stack. - 5The stack stays non-decreasing in height — that invariant is why each popped bar's reach is exactly known.
Use this pattern when
- Maximum-area / span problem where each element's value is a height and neighbours bound its reach
- You need, for each element, the nearest strictly smaller element on the left and right
- Histogram, skyline, or 'maximal rectangle' in a binary matrix (run this per row)
- Any 'expand while neighbours are at least as tall' computation in one pass
Choose another pattern when
- You only need the single tallest bar → that's just a max, no stack
- Bars can be negative / it's not an area problem → monotonic-stack framing doesn't apply
- You need every rectangle, not the largest → enumeration, not this greedy pop
- The array is tiny and clarity matters more than speed → brute force is fine
Interview takeaway
The monotonic stack answers 'how far can this height extend?' for every bar in one pass. The key realisation: a bar's rectangle is fixed exactly when a shorter bar appears on its right — that's the moment to pop and measure. This is the engine behind Maximal Rectangle, Trapping Rain Water, and Next Greater Element.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical monotonic-stack 'nearest smaller on both sides' computed in one pass. Recognise it whenever each element's answer is bounded by its nearest smaller/greater neighbours and you want all of them in O(n). Same engine as Maximal Rectangle, Trapping Rain Water, and Next Greater Element.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Maximal RectangleComing soonBuild a histogram per matrix row (running counts of 1s) and run this algorithm on each row.
- Largest Rectangle in Histogram (LeetCode)Coming soonThe identical problem — same monotonic-stack solution.
- Trapping Rain WaterComing soonAlso a monotonic stack of bars, but you accumulate trapped water between walls instead of areas.
- Next Greater Element IComing soonThe bare monotonic-stack skeleton: nearest greater neighbour, no width arithmetic.