Largest Rectangle in Histogram — The Hardest Monotonic Stack Problem Explained

Problem Statement#

Given an array of integers heights representing a histogram where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Constraints:

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

Input:  heights = [2,1,5,6,2,3]
Output: 10

Input:  heights = [2,4]
Output: 4

Why This Problem Matters#

Largest Rectangle in Histogram is the definitive hard monotonic stack problem. Google uses it in interviews to distinguish candidates with genuine algorithmic depth from those who memorized easy-to-medium patterns. The problem appears directly as a subproblem in LC 85 Maximal Rectangle — one of the hardest 2D DP problems — meaning mastering this one unlocks two hard problems simultaneously.

The key interviewer signal: can you reason about what the stack represents? With easy and medium stack problems, you can sometimes rely on intuition. Here, you must explain precisely why an increasing stack is used, what each pop computes, and why the width formula current_index - stack[-1] - 1 is correct. Candidates who cannot articulate this fail even with a working solution.

The sentinel technique (appending a 0-height bar to flush the stack) is also tested — interviewers often ask "what happens without the sentinel?" as a follow-up.

The Core Insight#

For each bar, consider the largest rectangle that uses that bar as its limiting (shortest) bar. This rectangle extends as far left and right as possible while all bars in range are at least as tall.

For each bar i with height h, find:

• Left boundary: index of the first bar to the left that is SHORTER than h
• Right boundary: index of the first bar to the right that is SHORTER than h

Area = h * (right_boundary - left_boundary - 1).

A monotonic increasing stack computes exactly these boundaries in one pass. When bar i is shorter than the stack top, the stack top bar has found its right boundary (bar i), and its left boundary is the new stack top after popping. The increasing invariant guarantees this is correct.

Visual Dry Run#

Input: heights = [2, 1, 5, 6, 2, 3] with sentinel 0 appended

Result: 10. The sentinel index -1 at the stack bottom provides the left boundary when all other elements have been popped.

Solution (Optimal)#

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        heights = heights + [0]  # Sentinel to flush all bars at the end
        stack = [-1]             # Sentinel left boundary
        max_area = 0
 
        for i, h in enumerate(heights):
            while stack[-1] != -1 and heights[stack[-1]] >= h:
                height = heights[stack.pop()]
                width = i - stack[-1] - 1  # Left boundary is new stack top
                max_area = max(max_area, height * width)
            stack.append(i)
 
        return max_area

var largestRectangleArea = function(heights) {
    heights.push(0);  // Sentinel to flush remaining bars
    const stack = [-1];
    let maxArea = 0;
 
    for (let i = 0; i < heights.length; i++) {
        while (stack[stack.length - 1] !== -1 && heights[stack[stack.length - 1]] >= heights[i]) {
            const height = heights[stack.pop()];
            const width = i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
 
    return maxArea;
};

Time: O(n) — each bar is pushed once and popped at most once; 2n stack operations total Space: O(n) — stack holds at most n+1 indices

Common Mistakes#

• Using a decreasing stack instead of an increasing one — NGE problems use decreasing; rectangle area problems use increasing
• Wrong width formula: after popping, use i - stack[-1] - 1, not i - popped - 1; the left boundary is the new stack top, not the popped index minus one
• Forgetting the sentinel index -1 at the stack bottom — without it, you need a special case when the stack is empty after a pop
• Forgetting the trailing 0 sentinel — without it, bars forming an increasing sequence at the end are never popped and their rectangles are missed
• Using > instead of >= in the pop condition — equal-height bars should all be treated with the same right boundary

Interview Tips#

• Draw the histogram before coding — sketch the bars and rectangles; this shows geometric understanding and helps catch bugs early
• Explain the invariant before coding: "I maintain an increasing stack of bar indices; when a shorter bar arrives, the stack top has found its right boundary and the new stack top is its left boundary"
• Walk through the width formula explicitly: "When I pop index j, right boundary is i, left boundary is stack[-1] after the pop. Width = i - stack[-1] - 1 because both boundary bars are excluded"
• Derive the formula if you forget: the rectangle spans indices stack[-1]+1 to i-1 inclusive, so width = (i-1) - (stack[-1]+1) + 1 = i - stack[-1] - 1

Follow-up Questions#

• How do you extend this to find the maximal rectangle in a binary matrix (LC 85)? For each row, build a cumulative height histogram where height resets to 0 on '0' cells. Apply this function per row. O(m*n) total.
• What if bar widths are not all 1? Store (index, width) pairs in the stack and accumulate widths across all popped bars instead of using the index difference formula.
• Can you solve this with prefix/suffix arrays instead of a stack? Yes: precompute left[i] and right[i] (previous and next shorter bar) using two separate stack passes. Same O(n) time with two passes.

Key Takeaways#

• Use an increasing monotonic stack for rectangle area; use a decreasing stack for next greater element — these are opposite directions.
• Width formula on each pop: right_boundary - left_boundary - 1, where right boundary is the current index and left boundary is the new stack top after popping.
• The sentinel index -1 at the stack bottom and sentinel height 0 appended to heights eliminate all edge cases cleanly.
• Mastering this problem directly unlocks LC 85 Maximal Rectangle, which reduces to running this algorithm per matrix row.
• The width formula i - stack[-1] - 1 is the single most common implementation error — derive it from first principles rather than memorizing it.
• Each bar is pushed once and popped at most once, giving O(n) amortized time across all iterations.
• Google uses this problem specifically to test whether candidates can explain the stack invariant and width formula, not just produce working code.