Largest Rectangle
Stacks & Queues: lesson 9 of 9
Every bar waits on the stack until both its walls are known.
Lesson 9 of 9 · 7 min
Largest Rectangle
Step 1 of 14
A rectangle is height times width. The height is given — the width is what has to be discovered.
The Idea
A rectangle is a height times a width, and the width is what is hard: how far left and right can this bar stretch before something shorter blocks it?
Keep a stack of bars with increasing heights. A shorter bar arriving is the right wall for every taller bar on the stack — and the bar left underneath is the left wall.
Real-World Example
Hanging one banner across a row of shopfronts of different heights. The banner can only be as tall as the shortest front it crosses, so each shop's best banner ends at its first shorter neighbour on either side.
The Code
def largest_rect(h):
stack, best = [], 0 # indexes, their heights increasing
for i, x in enumerate(h + [0]): # the trailing 0 flushes the stack
while stack and h[stack[-1]] >= x:
top = h[stack.pop()] # this bar can grow no further right
left = stack[-1] + 1 if stack else 0
best = max(best, top * (i - left)) # it reaches back to `left`
stack.append(i)
return best
print(largest_rect([2, 1, 5, 6, 2, 3])) # 10 -- bars 5 and 6, width 2
print(largest_rect([3, 3, 3])) # 9Your turn
Fill in the blank.
h = [2, 1, 5, 6, 2, 3]
stack, best = [], 0
for i, x in enumerate(h + [0]):
while stack and h[stack[-1]] >= x:
top = h[stack.pop()]
left = ___
best = max(best, top * (i - left))
stack.append(i)
print(best) # should print 10Mini quiz
1 / 3