Skip to content

84. Largest Rectangle in Histogram

On LeetCode ->

Problem

Given bar heights of a histogram, find the maximum area of a rectangle formed by one or more contiguous bars.

heights = [2, 1, 5, 6, 2, 3] -> 10
# Bars [5, 6] support a rectangle of height 5 and width 2.

Key trick

Use a monotonic increasing stack; when a shorter bar appears, pop every taller bar and compute the largest rectangle for which that popped bar is the limiting height.

Trap

  • Two pointers do not work because shrinking an endpoint does not efficiently reveal the minimum height of the remaining interval.
  • The width of a popped bar extends from its saved start index up to, but not including, the current index.
  • A final sentinel height is needed to process bars left in the stack.

Why is it interesting?

It turns an apparently quadratic range-minimum problem into a linear scan by determining each bar's maximal usable width exactly once.

Python solution

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []
        best = 0
        n = len(heights)

        # Each pair stores the earliest index at which its height can start.
        # The zero-height sentinel flushes all remaining bars.
        for i in range(n + 1):
            h = heights[i] if i < n else 0
            start = i

            while stack and stack[-1][1] > h:
                idx, height = stack.pop()
                best = max(best, height * (i - idx))
                start = idx

            stack.append((start, h))

        return best
  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)

Comment on my solution

Your exhaustive interval idea is correct, but the heap makes it \(O(n^2 \log n)\) and therefore exceeds the limit for \(10^5\) bars.

  • Every pair of interval endpoints is still examined.
  • The heap is unnecessary even for brute force: a running minimum would reduce it to \(O(n^2)\).
  • The two-pointer observation is correctly rejected because the limiting height may lie anywhere inside the interval.
  • The required improvement comes from reversing the viewpoint: for each bar, find the widest interval in which it is the minimum.
# Ideas:
# - we're looking for 3 edges left, right, top
#   - 2 pointers at start and end
#   - shrink inward side with smaller height
#   - keep a global best
#   - NOT good idea (we need to know the minimum in the sliding range)
# - as we need a common minimum, maybe use heap
# - what about sorting as preprocessing?
# - brut force using heap for min in range is O(n^2 * log n)
# - maybe a variation on Kadane's algo
#   - instead of best sum
#     - track best area so far
#     - current area
#     - need current_min_height for that
# - No good idea so far.  Let's implement brute force at least.

import heapq

# WRONG
# Time Limit Exceeded: 87/99 testcases passed
class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        best = 0
        for i in range(n):
            h1 = heights[i]
            heap = [h1]
            best = max(best, h1)
            for j in range(i + 1, n):
                h2 = heights[j]
                heapq.heappush(heap, h2)
                best = max(best, (j - i + 1) * heap[0])
        return best