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() -> str:
nums = [2, 1, 5, 6, 2, 3]
print(f"Initial histogram: {nums}")
s = Solution()
result = s.solve(nums)
print(f"Final result: {result}")
return f"Largest rectangle in {nums} -> {result}"
if __name__ == "__main__":
demo()
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.",
)