← Back to DSA Animator
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.