Find the largest rectangle that can be formed in a histogram.
This problem follows the Monotonic Stack pattern, commonly found in the Stack category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Maintain increasing stack. On smaller bar, pop and calculate areas using stack for widths.
The width calculation uses the stack to find the left boundary — when you pop, everything between the new stack top and current index has height >= the popped bar.
stack = []
maxArea = 0
for i in range(len(heights) + 1):
h = heights[i] if i < len(heights) else 0
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
maxArea = max(maxArea, height * width)
stack.push(i)
return maxAreaPractice Largest Rectangle in Histogram and similar Stack problems with flashcards. Build pattern recognition through active recall.
Practice this problem