Largest Rectangle in Histogram
Find the largest rectangle area in a histogram.
Pattern fit
The stack helps each bar find the first smaller boundary on both sides, which is exactly what you need to compute its maximal width.
Key observation
When a bar is popped, the current index is its first smaller bar on the right, and the new stack top becomes its first smaller bar on the left.
Target complexity
O(n) / O(n)
How to break down the solution cleanly
The stack helps each bar find the first smaller boundary on both sides, which is exactly what you need to compute its maximal width.
When a bar is popped, the current index is its first smaller bar on the right, and the new stack top becomes its first smaller bar on the left.
Decide what unresolved property the stack maintains.
Push indices while the monotonic invariant holds.
Reference implementation
Python# Generic pattern template
stack = []
for i, value in enumerate(nums):
while stack and nums[stack[-1]] < value:
prev_index = stack.pop()
# value is the next greater for prev_index
stack.append(i)
Common pitfalls
Forgetting sentinel bars and missing the final stack cleanup.
Using heights without tracking their boundaries via indices.
Common follow-ups
How does adding sentinel zeroes simplify the code?
Why is the width computed from the new stack top after pop?
Continue with related problems
Build repeatable depth inside the Monotonic Stack cluster before moving on.