Classic example
Input
heights = [2,1,5,6,2,3]
Output
10
The largest rectangle has area 10 using heights 5 and 6 (width 2, height 5).
Full lesson preview
Find the largest rectangle in a histogram
Given bar heights of a histogram, compute the area of the largest rectangle that can be formed.
Python practice25 minStacks & QueuesAdvancedLast updated March 27, 2026
Problem statement
Given an array heights representing the heights of histogram bars of width 1, return the area of the largest rectangle that can be formed using contiguous bars. Implement an efficient O(n) algorithm using a stack.
Task
Use a monotonic stack to compute the largest rectangular area in O(n) time and O(n) space.
Examples
Input format
A list of non-negative integers heights.
Output format
An integer representing the maximum rectangular area.
Constraints
1 <= len(heights) <= 10^5. 0 <= heights[i] <= 10^9. Expected O(n) time, O(n) space solution.
Samples
Sample 1
Input
[2,4]
Output
4
Two bars, max area is 2*2 = 4 choosing both bars with min height 2.