Largest Rectangle in Histogram
Problem statement
A histogram is given as a list heights of non-negative integers, one bar per value, each bar one unit wide and standing next to the previous one. Return the area of the largest axis-aligned rectangle that fits entirely inside the histogram.
A rectangle spanning bars i to j can be at most as tall as the shortest bar in that range, so its area is (j - i + 1) · min(heights[i..j]).
Examples
Example 1
Input: heights = [2,4,4,1,3]
Output: 8
Explanation: The two bars of height 4 make a 2 × 4 rectangle. The widest option, height 1 across all 5 bars, gives only 5.
Example 2
Input: heights = [2,1,2]
Output: 3
Explanation: No single bar beats a height-1 rectangle across all three bars.
Hints
Approach
Monotonic stack. Keep a stack of indices whose heights increase from bottom to top. Walk the bars, plus one imaginary bar of height 0 at the end that flushes everything.
When the current bar is shorter than the bar on top of the stack, the top bar can't extend any further right. Pop it: its rectangle is bounded on the right by the current index i, and on the left by the new stack top (the nearest shorter bar to its left), or by the start of the array if the stack is empty. Its width is i - stack[-1] - 1 (or i), and its area is that width times its height. Keep popping while the top is taller, then push i.
Each index is pushed and popped once.
O(n)Space O(n)def largest_rectangle_area(heights): stack = [] # indices, heights increasing best = 0 for i, h in enumerate(heights + [0]): while stack and heights[stack[-1]] > h: height = heights[stack.pop()] width = i if not stack else i - stack[-1] - 1 best = max(best, height * width) stack.append(i) return best print(largest_rectangle_area([2, 4, 4, 1, 3]))print(largest_rectangle_area([2, 1, 2]))Follow-up questions
- Largest rectangle of 1s in a binary matrix (Maximal Rectangle: build a histogram per row and reuse this).
- Return the start and end index of the best rectangle, not just its area.
Frequently asked questions
It is the classic problem for the monotonic stack, and it comes up in SWE-grade loops on its own and as a step inside Maximal Rectangle. A practical reading: given per-minute available capacity, what is the largest block of work (duration times guaranteed capacity) you can schedule without ever exceeding it?
It is shorter than every real bar, so it forces the stack to pop everything left on it. Without it you would need a second loop after the main pass to process the bars that never met a shorter bar on their right.
With the > comparison, an equal bar doesn't pop the earlier one, so the first of the equal bars gets popped later with a width that covers all of them. The later ones may be popped with shorter widths, but the maximum is still found.