LeetEye LeetEye
Medium Stack ~5 min

Largest Rectangle in Histogram

stack largest-rectangle-in-histogram

Problem

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

Examples

Example 1
Input: heights = [2,1,5,6,2,3]
Output: 10
Rectangle with height 5 and width 2 (indices 2-3) = 10
Example 2
Input: heights = [2,4]
Output: 4
Key Insight

For each bar, find how far it can extend left and right.

Monotonic increasing stack: when a shorter bar appears, all taller bars on stack have found their right boundary. Pop, compute width = right - left - 1, track max area.

How to Approach This Problem

Pattern Recognition: When you see keywords like largest rectangle in histogram stack, think Stack.

Step-by-Step Reasoning

1 A rectangle of height h starting at bar i can extend to bar j if:
Answer: heights[j] ≥ h
As long as bars are at least height h, the rectangle continues.
2 The maximum rectangle using bar i as the shortest bar:
Answer: Extends to first shorter bar on each side
Rectangle height is limited by bar i. It extends until a shorter bar blocks it.
3 We maintain bars in increasing height order because:
Answer: When a shorter bar appears, we can compute rectangles for all taller bars
A shorter bar terminates all taller bars' extensions to the right. We process them now.
4 For a bar popped from the stack, its left boundary is:
Answer: The new stack top's index (or -1 if empty)
The bar below it on the stack is the first shorter bar to its left. If stack becomes empty, it can extend to index 0 (left boundary = -1).
5 For a bar popped because of bar at index i, its right boundary is:
Answer: i
Bar at index i is the first shorter bar to its right. Right boundary = i (exclusive).
6 If left boundary (exclusive) is L and right boundary (exclusive) is R: Width = ?
Answer: R - L - 1
Bars from L+1 to R-1 are included. Count = (R-1) - (L+1) + 1 = R - L - 1.

Solution

def largestRectangleArea(heights: List[int]) -> int:
    stack = []  # Stack of indices
    max_area = 0
    
    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx  # Extend left boundary
        stack.append((start, h))
    
    # Process remaining bars (extend to end)
    for idx, height in stack:
        max_area = max(max_area, height * (len(heights) - idx))
    
    return max_area

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Stack problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye