Largest Rectangle in Histogram

Difficulty: Hard

Problem

A skyline is drawn as bars, each of width 1, with the bar heights given in the integer array heights. Find the area of the biggest rectangle that fits inside the skyline, where the rectangle must be built from consecutive bars.

Example

Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: Using bars at indices 2 and 3 (heights 5 and 6), the shortest is 5 and the width is 2, so the area is 5 x 2 = 10. No other run of consecutive bars beats it: all six bars give 1 x 6 = 6, and bars 2 to 5 give 2 x 4 = 8.

Brute-force approach

For each bar, expand left and right to find how far the rectangle of that bar's height can extend. Calculate area and track the maximum.

Steps

  1. For each bar i:
  2. Expand left while bars have height ≥ heights[i]
  3. Expand right while bars have height ≥ heights[i]
  4. area = heights[i] × (right - left + 1)
  5. maxArea = max(maxArea, area)

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • For each bar, expanding left and right is O(n) in the worst case
  • Total: O(n²), too slow for large inputs
  • Redundant: neighboring bars re-check overlapping ranges

Optimal approach

Key insight: A bar's rectangle ends when a shorter bar appears to its right. The stack tracks bars that haven't found their right boundary yet.

Use a monotonic increasing stack of indices. When a shorter bar is encountered, pop taller bars and calculate their areas using the current index as the right boundary.

Steps

  1. Initialize empty stack and maxArea = 0
  2. For each index i (including a virtual index n with height 0):
  3. While stack not empty AND current height < height at stack top:
  4. Pop the top index, get its height h
  5. Width = i - stack.top - 1 (or i if stack empty)
  6. maxArea = max(maxArea, h × width)
  7. Push i onto stack
  8. Return maxArea

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function largestRectangle(heights):
    stack = []  // stores indices
    maxArea = 0
    
    for i = 0 to len(heights):  // include one extra
        currHeight = 0 if i == len(heights) else heights[i]
        while stack not empty and currHeight < heights[stack.top]:
            h = heights[stack.pop()]
            w = i if stack is empty else (i - stack.top - 1)
            maxArea = max(maxArea, h * w)
        stack.push(i)
    
    return maxArea

Hints

  • For each bar, think about how far left and right it can extend
  • A monotonic increasing stack helps find the boundaries efficiently
  • When a shorter bar appears, taller bars on the stack can't extend further right
  • Process an extra 'height 0' at the end to flush remaining bars from the stack

Complexity questions

What is the time complexity of expanding left and right from each bar?

O(n²). For each of n bars, expansion can take up to O(n) → O(n²) total.

Why is the stack approach O(n)?

Each bar is pushed once and popped once → total 2n operations. Each of n bars is pushed exactly once and popped at most once. Total operations: O(2n) = O(n).

What is the worst-case stack size?

O(n). If heights are strictly increasing, all n indices remain on the stack → O(n).

Check your understanding of Largest Rectangle in Histogram

What does the 'largest rectangle in a histogram' mean?

The largest rectangular area that can be formed using contiguous bars, where the rectangle's height is limited by the shortest bar in the range. We're looking for the biggest rectangle that fits inside the histogram. It must use contiguous (adjacent) bars, and its height can't exceed the shortest bar in the chosen range.

For heights = [2, 1, 5, 6, 2, 3], what is the area of the rectangle formed by bars at indices 2 and 3?

10 (min(5, 6) × 2). The rectangle's height is limited by the shortest bar in the range: min(5, 6) = 5. The width is 2 bars. So area = 5 × 2 = 10.

Why can't we form a rectangle of height 5 using bars at indices 1, 2, and 3 (heights 1, 5, 6)?

Because bar at index 1 has height 1, which is less than 5. The rectangle can't be taller than the shortest bar. A rectangle spanning bars 1–3 can only be as tall as the shortest bar in that range, which is height 1. The rectangle height is always limited by the shortest bar in the chosen contiguous range.

Related problems

Keep practising