LeetCode 84: Largest Rectangle In Histogram — Step-by-Step Visual Trace

Source: Dev.to

Problem

Find the area of the largest rectangle that can be formed in a histogram represented by an array of bar heights. Each bar has width 1 and the rectangle must be formed by consecutive bars.

Approach

Use a monotonic stack to track indices of bars in increasing height order. When a shorter bar is encountered, calculate rectangles using previously stored taller bars as heights, with widths determined by the current position and the stack contents.

Complexity

• Time: (O(n))
• Space: (O(n))

Code

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        max_area = 0

        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        while stack:
            height = heights[stack.pop()]
            width = len(heights) if not stack else len(heights) - stack[-1] - 1
            max_area = max(max_area, height * width)

        return max_area