Largest Rectangle in Histogram — Monotonic Stack Visualization

The Problem

Given an array of integers heights representing the histogram's bar heights where each bar has a width of 1, find the area of the largest rectangle in the histogram.

Example: For heights = [2,1,5,6,2,3], the largest rectangle has area 10 (formed by bars at indices 2 and 3, each of height 5, giving width 2 × height 5 = 10).

The key insight is that a monotonic increasing stack tracks potential rectangle starting positions. When a shorter bar appears, all taller bars on the stack can no longer extend right, so we calculate their areas.

Interactive Visualization

Heights Array (comma-separated)

Preset

Speed:

Max Area: 0

Current Index (i)

Current Height

Last Area

Max Area

Histogram & Rectangle Overlay

Monotonic Stack (index, height)

Empty

Code

fun largestRectangleArea(heights: IntArray): Int {    val stack = ArrayDeque<Pair<Int, Int>>()    var maxArea = 0    for ((i, h) in heights.withIndex()) {        var start = i        while (stack.isNotEmpty() && stack.last().second > h) {            val (idx, height) = stack.removeLast()            val area = height * (i - idx)            maxArea = maxOf(maxArea, area)            start = idx        }        stack.addLast(Pair(start, h))    }    for ((idx, height) in stack) {        val area = height * (heights.size - idx)        maxArea = maxOf(maxArea, area)    }    return maxArea}

def largestRectangleArea(heights):    stack = []    max_area = 0    for i, h in enumerate(heights):        start = i        while stack and stack[-1][1] > h:            idx, height = stack.pop()            area = height * (i - idx)            max_area = max(max_area, area)            start = idx        stack.append((start, h))    for idx, height in stack:        area = height * (len(heights) - idx)        max_area = max(max_area, area)    return max_area

Status & Log

Press Step or Play to begin.

How It Works

Key Insight

We maintain a monotonic increasing stack of (index, height) pairs. The stack invariant is that heights are always in non-decreasing order from bottom to top. When we encounter a bar that is shorter than the stack's top, we know the taller bar can no longer extend to the right — so we pop it and compute the rectangle it could form.

Algorithm Steps

Initialize: Create an empty stack and set max_area = 0.
Iterate: For each bar at index i with height h, set start = i.
Pop taller bars: While the stack is non-empty and the top height exceeds h, pop (idx, height). The rectangle for that bar has width i - idx and height height. Update max_area and set start = idx (the current bar can extend back to where the popped bar started).
Push: Push (start, h) onto the stack. The start index may be earlier than i because the current bar could extend left over all the popped bars.
Remaining stack: After the loop, bars still on the stack extend all the way to the end of the array. For each (idx, height), the rectangle has width len(heights) - idx.

Why Monotonic Increasing?

The stack only holds bars in increasing height order. A taller bar on top can always extend right as long as subsequent bars are at least as tall. The moment a shorter bar arrives, we resolve all taller bars on the stack because their maximum rightward extent is now known. This guarantees every bar is pushed and popped at most once, giving us O(n) amortized time.

Complexity

Time O(n)

Space O(n)

Each bar is pushed onto the stack exactly once and popped at most once, so the total number of stack operations is O(n). The stack itself can hold up to n entries in the worst case (e.g., a sorted ascending array), giving O(n) space.