← DSA Atlas
Dedicated problem page · #84

Largest Rectangle in Histogram

HardMonotonic Stack and Monotonic QueueLargest rectangle via nearest smaller barsMonotonic increasing stack
Solve on LeetCode ↗
84
HardMonotonic Stack and Monotonic QueueMonotonic increasing stackLargest rectangle via nearest smaller bars

Largest Rectangle in Histogram

Given an array of integers heights representing the bar heights of a histogram where each bar has width 1, return the area of the largest rectangle that can be formed within the histogram.

Open official problem prompt ↗
In plain English

Find the single widest-times-tallest rectangle that fits under the histogram's skyline.

Picture it like this

Think of pouring water columns of different heights. Each column can spread sideways until it bumps into a shorter neighbor; the biggest puddle of uniform depth is the answer.

Example
Input
heights = [2, 1, 5, 6, 2, 3]
Output
10
Why
The bars of height 5 and 6 form a rectangle of height 5 spanning 2 columns, giving area 5 x 2 = 10, the maximum possible.
Constraints
1 <= heights.length <= 10^50 <= heights[i] <= 10^4
Pattern lesson

See the pattern, then code

Largest rectangle via nearest smaller bars
Recognition clue

Maximizing a rectangle bounded by bar heights, where each bar can extend left and right until it hits a shorter bar, is the classic monotonic-stack histogram problem.

↗
Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. A bar of height h can widen left and right until it meets the first strictly shorter bar on each side. If we process bars left to right with an increasing stack, popping a bar tells us its right boundary, and the index stored beneath tells us its left boundary.

New words, made simpleKnow these before the algorithm
Nearest smaller element
For each bar, the closest bar to its left and right that is strictly shorter; these define how far the bar can stretch.
Increasing stack
A stack kept sorted by non-decreasing height, so a shorter incoming bar triggers pops that finalize taller bars' widths.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute force pair of bounds

Quadratic and far too slow for n up to 10^5.

For every pair (i, j) take the minimum height in between and compute area.

Time O(n^2)Space O(1)
Best choiceMonotonic increasing stack

Linear time with one push and one pop per bar.

Each bar is finalized exactly when the first shorter bar to its right appears; the stored start gives the left boundary.

Time O(n)Space O(n)
The rule we keep true

Invariant

Heights on the stack are non-decreasing from bottom to top, and each stored start index is the leftmost column that bar can still extend back to.

Why this is correct

Reasoning

When bar h is popped by a shorter bar at index i, i is its right boundary (first shorter bar to the right) and its stored start is its left boundary (it inherited the index of everything it was taller than). So height x (i - start) is the exact maximal rectangle with that bar as the limiting height, and every bar gets its turn.

The algorithm in three movesSay these aloud before coding
1Maintain a stack of (start_index, height) pairs in increasing height order

at i=4 (h=2), pop (3,6): area 6x1=6

2When the current bar is shorter than the stack top, pop it and compute area = height x (current_index - start)

pop (2,5): area 5x(4-2)=10 -> max

3Carry the popped start index leftward so the shorter current bar can extend back over that span

current bar 2 extends back to start=2

4After the scan, settle remaining bars using the array length as the right boundary

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
20
11
52
63
24
35
1 · Read5 then 6
2 · AskAre they taller than the top?
3 · Update statestack = [(0,1),(2,5),(3,6)]
4 · ResultBoth pushed since heights keep increasing.
Key takeaway

Bars 5 and 6 (indices 2-3) yield the winning 5 x 2 = 10 rectangle when height 2 arrives.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-7Track a rewind start

    start begins at i but moves left as we pop taller bars, capturing how far the current shorter bar can reach back.

  2. 2
    Lines 8-11Finalize taller bars

    Every stacked bar taller than h has met its right wall; compute its area and absorb its start.

  3. 3
    Lines 14-16Settle survivors

    Bars still on the stack never met a shorter bar to the right, so their right boundary is n.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single bar returns its own height
  • Strictly increasing heights only resolve in the final flush loop
  • A zero-height bar resets everything, splitting the histogram
!

Common beginner mistakes

  • Forgetting the final flush loop, which drops the tallest surviving bars
  • Losing the inherited start index, which produces widths that are too narrow
  • Using >= instead of > when popping, which double counts equal-height runs incorrectly
Check your understanding

When a bar is popped, why is the current index i its correct right boundary?

More in Monotonic Stack and Monotonic Queue

#739Daily TemperaturesNext greater element#85Maximal RectangleRow-by-row histogram reduction#316Remove Duplicate LettersLexicographically smallest subsequence with each letter once#456132 Pattern132 pattern detection#496Next Greater Element INext greater element with lookup indirection#503Next Greater Element IINext greater element (circular)