Leetcode - 84. Largest Rectangle in Histogram

Hard

Dec 22, 2025

#stack

#math

84. Largest Rectangle in Histogram

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 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

1 <= heights.length <= 105
0 <= heights[i] <= 104

Constraints:

Notes

Intuition

A monotonic increasing stack tracks bars that could be the height of a rectangle extending to the right. When a shorter bar appears, taller bars can no longer extend further—we calculate their maximum rectangle and pop them.

Implementation

Iterate through bars (plus a sentinel height of 0 to flush the stack). Maintain a stack of indices in increasing height order. When the current bar is shorter than the stack's top, pop and calculate the area using that bar's height. The width extends from the new stack top (or -1 if empty) to the current index. Track the maximum area.

Edge-cases

When the stack is empty after popping, the left boundary is -1 (the bar extends to the start). The sentinel value at the end ensures all remaining bars are processed.

Time: O(n) — each bar pushed and popped at most once
Space: O(n) — stack in worst case (ascending heights)

Complexity

Solution

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        max_area = 0
        for i in range(len(heights) + 1):
            curr = heights[i] if i < len(heights) else 0 # sentinel height of 0 to flush the stack
            while stack and curr < heights[stack[-1]]:
                h_idx = stack.pop()
                h = heights[h_idx]
                left_idx = stack[-1] if stack else -1
                w = i - left_idx - 1
                max_area = max(max_area, h * w)
            stack.append(i)

        return max_area
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()