84. Largest Rectangle in Histogram

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Stack-based (Monotonic Stack)	Use a stack to track indices and heights. When current height is smaller than stack top, pop elements and calculate area using the popped height. The width is determined by the distance between current index and the updated index from popped elements. This ensures we find the maximum rectangle for each height efficiently by maintaining increasing heights in the stack.	\(O(n)\)	\(O(n)\)

Implementation

PythonJavaScriptGo

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack: List[Tuple[int, int]] = []  # [(idx, height)]

        max_h = -float("inf")
        for curr_i, curr_h in enumerate(heights):

            updated_i = curr_i

            while stack and curr_h < stack[-1][1]:
                prev_i, prev_h = stack.pop()
                updated_i = prev_i
                w = curr_i - prev_i
                max_h = max(max_h, prev_h * w)

            stack.append((updated_i, curr_h))


        for i, h in stack:
            w = len(heights) - i
            max_h = max(
                max_h,
                h * w
            )

        return max_h