#27 Hard Time O(n) Space O(n) Animated

Largest Rectangle in Histogram

Find the largest rectangle in a histogram.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern LIFO state for unresolved work

Keep only items whose matching decision has not been made yet.

Approach: Monotonic Increasing Stack

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Keep only items whose matching decision has not been made yet.

Common Pitfall

Check that the stack is non-empty before reading its top.

Description

Find the largest rectangle in a histogram.

Constraints

Time Complexity: O(n)
Space Complexity: O(n)

Solution — Monotonic Increasing Stack

TimeO(n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Read one item at a time.
Push unresolved work.
Match or remove work when its partner arrives.
Validate the final stack state.

def largestRectangleArea(heights):
    maxArea = 0
    stack = [] # pair: (index, height)
    
    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            index, height = stack.pop()
            maxArea = max(maxArea, height * (i - index))
            start = index
        stack.append((start, h))
        
    for i, h in stack:
        maxArea = max(maxArea, h * (len(heights) - i))
        
    return maxArea

Car Fleet

Largest Rectangle in Histogram

Steps

Description

Constraints

Tags

Solution — Monotonic Increasing Stack