Monotonic Stack — Largest Rectangle in Histogram

What does it solve?

Given bar heights, find the largest rectangle that fits entirely under the histogram. Brute force tries every pair of bars for O(N²). An increasing monotonic stack nails it in one pass.

Key insight: every maximal rectangle has some bar as its shortest member. For each bar as the limiting height, the width stretches from just after its previous smaller bar to just before its next smaller bar. Keep a stack of indices with increasing heights. When a shorter bar arrives, it's the "next smaller" for everything taller on top: pop each, and the popped bar's width is bounded left by the new stack top. Area = height × width; track the max.

The core idea

// increasing stack of indices; sentinel 0 at end
for i in 0..n (h[n]=0):
  while stk && h[top] > h[i]:
    H = h[pop]
    W = stk ? i-top-1 : i
    best = max(best, H*W)
  push i

Complexity

Time complexity

O(N)

Each bar is pushed once and popped once. The sentinel at the end flushes the stack. All the width math is O(1) per pop.

Space complexity

O(N)

The stack holds at most N indices (strictly increasing heights) plus a few scalars.

Histograms & edge cases

Live animation — pops compute each rectangle, best is tracked

current bar i in stack popping (rectangle) best so far

Histogram bars

Monotonic stack (indices, heights increasing bottom → top)

Current step detail

i = — stack = — last area = — best = —

Step — of —

—

scan pointer

height × width

—

last rectangle

last area

—

just computed

best area

—

maximum

Select a histogram and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	h[i]	Stack (heights)	Action	Area	Best

C++ implementation

largest_rectangle_histogram.cpp

#include <bits/stdc++.h>
using namespace std;

// Largest rectangle under a histogram via an increasing monotonic stack.
long largestRectangle(vector<int>& h) {
    int n = h.size();
    stack<int> st;      // indices, heights increasing
    long best = 0;

    for (int i = 0; i <= n; i++) {
        int cur = (i == n) ? 0 : h[i];   // sentinel 0 flushes the stack
        while (!st.empty() && h[st.top()] > cur) {
            int H = h[st.top()]; st.pop();
            // width: bounded by new top (prev smaller) and i (next smaller)
            int W = st.empty() ? i : (i - st.top() - 1);
            best = max(best, (long)H * W);
        }
        st.push(i);
    }
    return best;
}

int main() {
    vector<int> h = {2,1,5,6,2,3};
    cout << largestRectangle(h) << "\n"; // 10 (bars 5,6 -> 5*2)
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars