Largest Rectangle in Histogram

StackArrayMonotonic Stack

30 min

Problem Statement

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example

Example 1:

Input Heights:

Largest Area:

Solution

A monotonic stack is the key to solving this problem efficiently. The stack will store indices of the histogram bars in increasing order of their heights.

Algorithm Steps

Initialize a stack to store pairs of [index, height].
Iterate through the heights. For each bar, while the stack is not empty and the current bar's height is less than the height of the bar at the top of the stack:
- Pop from the stack. Calculate the area with the popped height. The width is the current index minus the index of the new top of the stack.
- Update the max area found so far.
Push the current bar's [index, height] onto the stack.
After the loop, process any remaining bars in the stack.

Histogram

Stack [index, height]

Max Area: 0

Start.

Largest Rectangle in Histogram Solution


class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        maxArea = 0
        stack = []  # pair: [index, height]

        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index
            stack.append((start, h))

        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))
        return maxArea