HARD

Largest Rectangle in Histogram

Given an array heights representing a histogram's bar heights, where each bar has width 1, return the area of the largest rectangle that fits entirely within the histogram.

Example

Input heights = [2,1,5,6,2,3]

Output 10

Key Pointers

For any bar, the largest rectangle using it as the shortest bar extends left and right until it hits something shorter — finding those boundaries is the whole problem.
A monotonic increasing stack (of index/height pairs) tracks bars whose right boundary hasn't been found yet; a shorter incoming bar finalizes rectangles for everything taller still on the stack.
When a bar is popped, its rectangle's left boundary is whatever's now on top of the stack — that's why the "start" gets carried forward instead of just using the popped index.

Step-by-Step Analysis

Create an empty stack (holding (start_index, height) pairs) and set max_area to 0.
For each index i, height h: while the stack's top has a height greater than h, pop it, compute its area as height * (i - start_index), update max_area, and remember its start_index as the new bar's own start.
Push (start, h) onto the stack.
After the loop, pop everything remaining, treating the width as extending to the end of the array (len(heights) as the right boundary), updating max_area each time.

Complexity

Time: O(n) — Space: O(n)

Code

def largestRectangleArea(heights: list[int]) -> int:
    stack = []  # (start_index, height) pairs
    max_area = 0

    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            index, height = stack.pop()
            max_area = max(max_area, height * (i - index))
            start = index
        stack.append((start, h))

    for index, height in stack:
        max_area = max(max_area, height * (len(heights) - index))

    return max_area

Code Explanation

How the solution above works, piece by piece.

The stack holds (start_index, height) pairs with heights increasing from bottom to top.
When bar h is lower than the top, the top bar's rectangle can't extend past i. Pop it and measure height * (i - index).
start = index: the new, shorter bar can extend left to where the popped bar began, so it's pushed with that earlier start.
After the loop, the bars still on the stack extend all the way to the end: measure them with len(heights) - index.
Each bar is pushed and popped once: O(n) time, O(n) space.

Visual Walkthrough

Running it on heights = [2, 1, 5, 6, 2, 3]:

The stack keeps bars in increasing height. When a shorter bar arrives, taller bars can't extend any further right, so they are popped and their rectangle is measured. Popping 5 at i = 4 gives 5 × 2 = 10, the answer.

largest rectangle

Video Explanation

NeetCode — LeetCode 84