DSA AnimatorDSA animations
Largest Rectangle in Histogram LC #84 Hard Monotonic Stack
Problem

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: Bars of height 5 and 6 span width 2 → area = 5×2 = 10.
Example 2
Input: heights = [2,4]
Output: 4
Explanation: The bar of height 4 alone gives area = 4×1 = 4.
Example 3
Input: heights = [1,1,1,1,1]
Output: 5
Explanation: All 5 bars of height 1 form a 1×5 = 5 rectangle.
Constraints: 1 ≤ heights.length ≤ 10⁵  |  0 ≤ heights[i] ≤ 10⁴
Try Examples
Custom:
Approach
Monotonic Increasing Stack: each bar extends rightward until a shorter bar is found
On pop: area = height × (i − stack.top − 1). Track maximum area seen.
Histogram
Monotonic Stack (index → height)
[ empty ]
Area Calculation
Press Play or Next Step to begin.
Best Area
Max Area Found
0
Variables
Index i
—
h (curr height)
—
Stack Top idx:h
—
maxArea
0
Step Logic
Select an example above and press Play.
🏆
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init empty stack, maxArea = 0. Iterate i from 0 to n (sentinel h=0 at i=n)
2
For each i, get h = (i==n) ? 0 : heights[i]
3
While stack not empty and h < heights[stack.top]: pop and compute area
4
Pop height, compute width = stack.empty ? i : i−stack.top−1, update max
5
Push i onto stack. Continue until all bars processed.
6
Return maxArea
Time
O(n)
Space
O(n)
Why Monotonic Stack Works

We maintain a monotonically increasing stack of bar indices. When a shorter bar arrives, every taller bar behind it can no longer extend rightward — so we pop each and compute the maximum rectangle it could form. The width is determined by the gap between the current index and the new stack top (left boundary). The sentinel h=0 at position n flushes all remaining bars at the end.

How to solve Largest Rectangle in Histogram

LeetCode 84 · Hard · Stack · Pattern: Monotonic Stack

Why the obvious approach is slow

Trying every pair of left and right edges is O(n²). For each bar, we really want how far it can stretch left and right while staying the shortest.

The key idea

Keep a stack of bar indexes with increasing heights. When a shorter bar arrives, the taller bars on the stack cannot stretch any further right. So pop them one by one: each popped bar is the height, and the width runs from the new top of the stack to the current index. A zero-height bar at the end flushes everything left on the stack.

Remember

Pop a bar when a shorter one arrives; that is when its width is known. Width runs from the new stack top to the current index.

Run the animation above on your own input, or watch the 1:40 video explanation of Largest Rectangle in Histogram with a dry run and Java code.

More Stack problems