Largest Rectangle in Histogram
Task example: Largest Rectangle in Histogram
Each number is the height of a bar with width 1. Find the greatest area of a rectangle that fits beneath consecutive bars. Return the area.
heights = [2,1,5,6,2,3] area = 10
The bars of height 5 and 6 form a rectangle of height 5 and width 2. Its area is 10. Heights may be zero; the demo accepts 1 to 24 bars.
View LeetCode 8401 / Brute force
Brute force: video explanation
heights = [2,1,5,6,2,3] area = 10
Prefer reading? Follow the steps below.
- Choose a left boundary. Extend the right boundary one bar at a time, keeping the minimum height seen in this interval.
- The rectangle height is that minimum. Its width is right - left + 1. Multiply them and update the best area.
- Repeat for every left boundary. For indices 2 through 3, the height is 5 and the width is 2, giving area 10.
Time complexity · O(n²)
There are n(n + 1)/2 intervals. Updating the running minimum takes constant time per interval.
Space complexity · O(1)
Only the boundaries, minimum height, and best area are stored.
PYTHONLive code trace
02 / Monotonic stack (optimal)
Monotonic stack: video explanation
heights = [2,1,5,6,2,3] area = 10
Prefer reading? Follow the steps below.
- Store (start, height) pairs with nondecreasing heights. Each pair describes a rectangle that can still extend to the right.
- When a shorter height arrives at index i, pop taller entries. Their width is i - left. Update the best area and pass the popped left boundary to the new height.
- An extra zero-height position finishes the remaining rectangles. At index 4, popping height 5 from start 2 produces 5 × (4 - 2) = 10.
The stack calculates areas when their right boundary becomes known, avoiding a separate scan for each interval.
Time complexity · O(n)
Each entry is pushed once and popped at most once. The total work is linear.
Space complexity · O(n)
An increasing histogram can place all n bars in the stack.
PYTHONLive code trace