Largest Bar Rectangle
Problem
A bar chart is described by a list of heights, where every bar has width one and they stand side by side with no gaps. Find the area of the largest rectangle that fits entirely inside the bars. The rectangle may span several neighbouring bars, but its height can never exceed the shortest bar it covers.
Examples
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Why: the bars of height 5 and 6 support a rectangle two wide and five tallInput: heights = [2, 4]
Output: 4
Why: one tall bar beats the two-wide rectangle of height twoInput: heights = []
Output: 0
Why: edge case, an empty chart holds no rectangleHints
0 / 3
Every candidate rectangle is capped by one particular bar, the shortest one it covers. So instead of choosing spans, consider each bar as the height of its own best rectangle.
For a given bar, its rectangle stretches left and right until it meets a strictly shorter bar. Finding those two walls for every bar is the whole problem, and rescanning for them is the slow part.
Walk the bars keeping a stack of positions whose heights never decrease. A bar shorter than the top means the top bar has just met its right wall, so pop it and measure it, taking its left wall from whatever position is now underneath. Append a zero-height sentinel bar so the stack is guaranteed to drain.
Solution
Each rectangle is limited by its shortest bar, so it is enough to compute, for every bar, how far it can stretch before hitting a shorter one on either side. A stack of positions with non-decreasing heights makes both walls appear exactly once: the incoming bar is the right wall of everything taller that it pops, and the position left underneath after the pop is the left wall. A zero-height sentinel at the end forces every remaining bar to be measured. Each position is pushed and popped once, so time is O(n) and space is O(n).
def largest_rectangle(heights):
stack = [] # positions with non-decreasing heights
best = 0
for i, h in enumerate(heights + [0]): # the sentinel drains the stack
while stack and heights[stack[-1]] >= h:
top = stack.pop()
# whatever is left underneath is the first shorter bar on the left
left = stack[-1] + 1 if stack else 0
best = max(best, heights[top] * (i - left))
stack.append(i)
return best
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # -> 10
print(largest_rectangle([2, 4])) # -> 4
print(largest_rectangle([])) # -> 0Stuck on the idea rather than the code? Largest Rectangle covers it.