Back to solutions

Largest Rectangle in Histogram

HardStack & Queue

Given bar heights of a histogram, find the area of the largest rectangle that fits entirely within it.

Open problem
Constraints
  • 1 <= n <= 10^5
  • 0 <= heights[i] <= 10^4

Monotonic increasing stack

Time O(n)Space O(n)

Keep a stack of indices with increasing heights. When a shorter bar appears, pop taller bars and compute the rectangle each can form using the current index as the right boundary and the new stack top as the left.

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

int largestRectangleArea(vector<int>& heights) {
    heights.push_back(0);
    stack<int> st;
    int best = 0;
    for (int i = 0; i < (int)heights.size(); i++) {
        while (!st.empty() && heights[st.top()] > heights[i]) {
            int h = heights[st.top()]; st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            best = max(best, h * w);
        }
        st.push(i);
    }
    return best;
}