Q33: Largest Rectangle in Histogram. - DSA Patterns (Multi-Lang)

In Simple Words: Monotonic Increasing Stack. When a shorter bar is encountered, pop bars and calculate area with height of popped bar and width between current index and new stack top.

Time: $O(N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def largestRectangleArea(heights: list[int]) -> int:
    stack = []  # (index, height)
    max_area = 0
    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx
        stack.append((start, h))
    for i, h in stack:
        max_area = max(max_area, h * (len(heights) - i))
    return max_area