What is the time and space complexity of Largest Rectangle in Histogram?

Time complexity: O(n). Space complexity: O(n).

Largest Rectangle in Histogram

Hard

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Largest Rectangle in Histogram

Approach

Keep indices of bars in increasing-height order. When a shorter bar appears, repeatedly pop taller bars and compute rectangle area where the popped bar is the limiting height. Use a trailing zero height to flush remaining bars.

Complexity Analysis

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

Pattern

Monotonic Stack (Increasing)

Why It Works

When a bar is popped, the current index is the first smaller bar on the right and new stack top is first smaller bar on the left, giving exact maximal width for that height.

Updated Feb 2026