Hard — Stack | Array | Monotonic Stack | Histogram
The Problem
Find the area of the largest rectangle that can be formed in a histogram represented by an array of bar heights. Each bar has width 1 and the rectangle must be formed by consecutive bars.
Approach
Use a monotonic stack to track indices of bars in increasing height order. When a shorter bar is encountered, calculate rectangles using previously stored taller bars as heights, with widths determined by the current position and stack contents.
Time: O(n) · Space: O(n)
Code
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
max_area = 0
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
while stack:
height = heights[stack.pop()]
width = len(heights) if not stack else len(heights) - stack[-1] - 1
max_area = max(max_area, height * width)
return max_area
Watch It Run
TraceLit — See exactly where your code breaks
Paste your LeetCode solution and see every pointer, variable, and data structure update step by step.
tracelit.dev
Open interactive visualization
Try it yourself: Open TraceLit and step through every line.
Built with TraceLit — the visual algorithm tracer for LeetCode practice.