Largest Rectangle in a Histogram

Problem. Given bar heights $h_0,\dots ,h_{n-1}$ each of width 1, find the largest axis-aligned rectangle fitting inside the histogram.

The key observation

Every maximal rectangle has some bar as its shortest bar. For bar $i$, the widest rectangle with height $h_i$ extends from the previous smaller bar to the next smaller bar:

${\text{area}}_i=h_i\cdot (\mathrm{nextSmaller}(i)-\mathrm{prevSmaller}(i)-1).$

So the answer is ${\max }_i{\text{area}}_i$, and the whole problem reduces to finding, for each bar, its previous and next smaller elements — a monotonic stack job.

The one-pass solution — $O(n)$

long long largestRectangle(vector<int> h) {
    h.push_back(-1);                                  // sentinel flushes the stack
    stack<int> st;
    long long best = 0;
    for (int i = 0; i < (int)h.size(); i++) {
        while (!st.empty() && h[st.top()] >= h[i]) {
            int height = h[st.top()]; st.pop();
            int left = st.empty() ? -1 : st.top();
            best = max(best, (long long)height * (i - left - 1));
        }
        st.push(i);
    }
    return best;
}

When bar $i$ pops bar $t$, we know:

• the next smaller than $t$ is $i$ (that is why it popped);
• the previous smaller than $t$ is the new stack top.

So both boundaries are available exactly at the moment of popping — which is why one pass suffices.

The sentinel -1 at the end flushes everything remaining, removing a separate cleanup loop.

The stack invariant

The stack always holds indices with strictly increasing heights: the bars that are still “open” because nothing shorter has appeared to their right yet. Each index is pushed once and popped once, so the total work is $O(n)$ despite the inner while.

Maximal rectangle in a binary matrix

Build, for each row, the histogram of consecutive 1s ending at that row, and run the histogram algorithm on each:

int maximalRectangle(vector<vector<int>>& g) {
    int n = g.size(), m = g[0].size(), best = 0;
    vector<int> h(m, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) h[j] = g[i][j] ? h[j] + 1 : 0;
        best = max(best, (int)largestRectangle(h));
    }
    return best;
}

$O(nm)$ — one of the neatest reductions in the subject: a 2D problem solved by $n$ instances of a 1D one, in linear total time.

Related problems, same technique

Problem	Stack use
Largest rectangle in a histogram	this page
Maximal rectangle of 1s in a matrix	row histograms
Largest square of 1s	a simpler $O(nm)$ DP suffices
Trapping rain water	layer decomposition
Sum of subarray minimums	count where each element is the minimum
Next greater element	directly
Stock span	previous greater
Remove $k$ digits for the smallest number	greedy with a stack
Maximum area under a skyline	same
Build a Cartesian tree in $O(n)$	the stack is the right spine

Sum of subarray minimums

// each element contributes h[i] * (i - left[i]) * (right[i] - i)

Use strict on one side and non-strict on the other so that ties are counted exactly once. This “count the subarrays each element dominates” pattern turns an $O(n^2)$ enumeration into $O(n)$.

Divide and conquer — the alternative

Find the minimum bar; the answer either spans the whole range at that height, or lies entirely to one side. With a sparse table for the minimum index, this is $O(n\log n)$ — and $O(n)$ if you build the Cartesian tree first, since the recursion is that tree.

Slower than the stack, but the divide-and-conquer view explains why the Cartesian tree and the monotonic stack are the same object.

Why it is worth knowing

It is the canonical monotonic-stack problem, and the “for each element, find the range where it is the minimum” framing solves an entire family of array problems. Once you see that framing, the stack code writes itself.

See also: Monotonic Stack · Trapping Rain Water · Range Minimum Query