Largest Rectangle in Histogram — Monotonic Stack O(n) [LC 84]

Problem Statement#

Given an array of integers heights representing the histogram bar heights (each width = 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#

LeetCode 84 is a hard problem that appears at Amazon, Google, and Microsoft. It is also the building block for Maximal Rectangle (LC 85) — a 2D extension of this problem. The monotonic stack solution teaches a powerful pattern: for each bar, find the nearest shorter bar on each side, which defines the maximum width over which that bar's height can extend.

The problem is harder than Daily Temperatures (LC 739) but uses the same "pop when invariant breaks" monotonic stack structure. If you've mastered LC 739, LC 84 is the natural next step.

The Core Insight#

For each bar, the rectangle it defines has:

• Height = heights[i]
• Width = (right boundary - left boundary - 1) where boundaries are the nearest shorter bars on each side

Monotonic increasing stack: Maintain a stack of indices with increasing heights from bottom to top. When we encounter a bar shorter than the stack top, the stack top can no longer extend rightward — compute its maximum rectangle.

When popping index mid:

• Height = heights[mid]
• Right boundary = current index i (the shorter bar that caused the pop)
• Left boundary = new stack top after popping (the next shorter bar to the left)
• Width = i - left_boundary - 1
• Area = height * width

Sentinel trick: Append a 0 at the end to flush all remaining stack elements at the end, and optionally prepend a -1 to simplify left-boundary calculation.

Visual Dry Run#

heights = [2, 1, 5, 6, 2, 3]

Append 0: [2, 1, 5, 6, 2, 3, 0]

Maximum area = 10.

Solution (Optimal)#

class Solution:
    def largestRectangleArea(self, heights):
        stack = [-1]   # sentinel for left boundary
        heights.append(0)  # sentinel to flush all at end
        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
                max_area = max(max_area, height * width)
            stack.append(i)
        heights.pop()   # restore original array
        return max_area

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

Time: O(n) — each index pushed and popped at most once Space: O(n) — stack holds at most n indices

Common Mistakes#

• Using > instead of >= when popping — equal height bars must also pop to correctly compute width (or be handled carefully)
• Forgetting the terminal 0 sentinel — without it, remaining bars on the stack at the end are never computed
• Width formula error: i - stack.top() - 1 not i - stack.top() — the boundaries are exclusive
• Not using -1 sentinel for left boundary — causes special case handling when stack is empty during width calculation
• Computing area for duplicates incorrectly — multiple bars with equal height should be handled by the >= pop condition

Interview Tips#

• State the core idea: "for each bar, find nearest shorter bars on both sides — those define the maximum width"
• Explain why the stack is monotonic increasing: "a taller bar can always extend as far as shorter bars to its left"
• Draw the histogram and visually show which bars become the left/right boundaries when a bar is popped
• Mention the sentinel trick (-1 and 0) to avoid edge cases — cleaner code in interviews
• Connect to Maximal Rectangle (LC 85): "apply this histogram algorithm to each row of the 2D matrix"

Follow-up Questions#

• How does this extend to Maximal Rectangle in a Binary Matrix (LC 85)? (Build a histogram for each row — heights accumulate downward; apply this algorithm to each row's histogram)
• What is the divide-and-conquer approach? (Find the minimum bar, recurse on both halves — O(n log n) average, O(n²) worst case)
• What is the brute force O(n²) approach? (For each bar, expand left and right until a shorter bar is found)
• Can you find the actual rectangle, not just its area? (Track which index caused each pop and the corresponding left boundary in the stack)
• What if bar widths are not all 1? (Multiply height by the actual width of each bar; same stack logic)

Key Takeaways#

• LeetCode 84 is asked at Amazon, Google, and Microsoft — builds directly toward Maximal Rectangle (LC 85)
• Monotonic increasing stack: when a shorter bar arrives, all taller bars on the stack can compute their maximum rectangle
• Width = current index - new stack top - 1 (after popping the bar being computed)
• Use sentinels: -1 at stack bottom and 0 appended to heights — eliminates all edge case handling
• Time O(n) — each index pushed and popped at most once; Space O(n) for the stack
• The >= pop condition (not >) handles equal-height bars correctly
• Mastering LC 84 is required for LC 85 (Maximal Rectangle) — the histogram sub-problem is applied row by row