Algorithm Notes
Summary: Largest Rectangle In Histogram — notes not yet curated.
Time: Estimate via loops/recurrences; common classes: O(1), O(log n), O(n), O(n log n), O(n^2)
Space: Count auxiliary structures and recursion depth.
Tip: See the Big-O Guide for how to derive bounds and compare trade-offs.
Big-O Guide
Source
"""
Largest Rectangle In Histogram
Given a histogram represented by an array of bar heights,
find the area of the largest rectangle in it.
"""
from interview_workbook.leetcode._registry import register_problem
from interview_workbook.leetcode._types import Category, Difficulty
class Solution:
def solve(self, heights) -> int:
"""Return maximum area of a rectangle in the histogram."""
stack = []
max_area = 0
heights.append(0)
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
heights.pop()
return max_area
def demo():
return str(Solution().solve([2, 1, 5, 6, 2, 3]))
register_problem(
id=84,
slug="largest_rectangle_in_histogram",
title="Largest Rectangle In Histogram",
category=Category.STACK,
difficulty=Difficulty.HARD,
tags=["stack", "monotonic stack"],
url="https://leetcode.com/problems/largest-rectangle-in-histogram/",
notes="Monotonic increasing stack to compute max rectangle area.",
)