Largest Rectangle in Histogram: how a monotonic stack finds first smaller boundaries and solves it in linear time

Learn the Largest Rectangle in Histogram solution: a linear-time monotonic stack method that finds first smaller boundaries, with explanation and C++ code.

Largest Rectangle in Histogram is one of those problems where the brute force path looks tempting, but the real breakthrough comes from reframing the objective. The trick is not to try all possible ranges or build a decision tree. Instead, you look at each bar and ask a single question: if this bar’s height is the bottleneck height of a rectangle, how wide can that rectangle stretch?

Problem in one line

Given heights of histogram bars, compute the area of the largest rectangle fully contained within the histogram. Example: for [2,1,5,6,2,3], the answer is 10 (formed by bars [5,6] with width 2 and height 5).

Naive approach that times out

Below is a recursive search that tries to accumulate ranges and keep track of the minimum height so far. It explores whether to start a new range or extend the current one, and updates the best area at each step. It works functionally, but it’s exponential in the worst case and does not scale.

class HistMax:
    def rect_max_area(self, bars: List[int]) -> int:
        best = 0
        def explore(pos, cur_min, span, arr):
            nonlocal best
            area_here = cur_min * span
            best = max(best, area_here)
            if pos < len(arr):
                if arr[pos] > cur_min:
                    explore(pos + 1, arr[pos], 1, arr)
                explore(pos + 1, min(arr[pos], cur_min), span + 1, arr)
        explore(0, float('inf'), 0, bars)
        return best

The core insight

The goal is simple: identify the index whose height defines the largest rectangle. The largest rectangle must use one of the existing heights as its limiting height. For a fixed index i with height heights[i], the rectangle that uses heights[i] as its height can extend to the left and right as long as all bars are at least heights[i]. That naturally leads to two boundaries: the first bar strictly shorter than heights[i] on the left, and the first bar strictly shorter on the right. Everything between those two shorter bars can support a rectangle of height heights[i].

That’s why the phrase matters: “For each index i, store the index of the first bar to the left and right, respectively, that is shorter than height[i].” Those two boundaries determine the maximal width for which heights[i] can serve as the rectangle’s height. Once you know these boundaries for every i, you can compute all candidate areas and take the maximum. A monotonic stack is a convenient way to discover those boundaries efficiently.

Efficient solution with a monotonic stack

The following implementation uses a stack of indices that maintains a nondecreasing sequence of heights. When a lower bar appears (or we hit the sentinel end), we know the popped index has found its right boundary, and the new stack top reveals the left boundary. The width is derived from those two. This runs in linear time with respect to the number of bars.

class Histogram {
 public:
  int maxRectArea(vector<int>& bars) {
    int result = 0;
    stack<int> idxs;
    for (int p = 0; p <= bars.size(); ++p) {
      while (!idxs.empty() &&
             (p == bars.size() || bars[idxs.top()] > bars[p])) {
        const int h = bars[idxs.top()];
        idxs.pop();
        const int w = idxs.empty() ? p : p - idxs.top() - 1;
        result = max(result, h * w);
      }
      idxs.push(p);
    }
    return result;
  }
};

Why the boundaries matter

For any index i, the left and right boundaries mark exactly how far you can stretch while keeping heights[i] as the controlling height. Outside those boundaries, a strictly shorter bar appears, which immediately reduces the feasible height below heights[i]. Therefore, the maximal rectangle “owned” by i is fully determined by those first shorter bars on both sides. Recording or discovering these boundaries for all i is sufficient to solve the problem.

Why you should care

This pattern appears in many array problems where you need “the first smaller/greater on the left/right.” Understanding it helps you recognize when a monotonic stack can collapse a brute force search into a linear pass. In practice, that shift is the difference between hitting timeouts and getting an optimal solution.

Takeaways

Frame the objective as choosing which index provides the height of the maximum rectangle. For that index, determine how far left and right you can expand until the first strictly smaller bar. Use a monotonic stack to find these boundaries efficiently and compute the best area on the fly.