Coding interview problems › Stack & Monotonic Stack

📚 Stack & Monotonic Stack Hard

Largest Rectangle in Histogram

Largest Rectangle in Histogram explained: an increasing stack finds where each bar's rectangle ends on both sides in O(n). Tested Python, live visual.

Also searched as: maximum area histogram · largest area under histogram stack · max rectangle in histogram

📚

Try it live Free

Stacks & the Monotonic Stack

Practise the monotonic stack mode on Next Greater Element and Daily Temperatures first; this problem is the same push-and-pop pattern, except each pop also measures a rectangle.

Open the playground →

The problem

Given the heights of bars in a histogram, each bar 1 unit wide, find the area of the largest rectangle that fits entirely inside the histogram.

Inputheights = [2, 1, 5, 6, 2, 3]
Output10

Bars of heights 5 and 6 give a rectangle of height 5 and width 2.

The key insight

The best rectangle uses some bar as its shortest bar, and stretches left and right until it hits a shorter one. Keep a stack of bar indices with increasing heights. When a shorter bar arrives, every taller bar on top has just found its right boundary, and the bar below it on the stack is its left boundary, so you can compute its full rectangle as you pop it.

Brute force first: Trying every pair of left and right ends and tracking the minimum height between them takes O(n²).

Step-by-step approach

  1. Append a bar of height 0 at the end so every bar eventually gets popped.
  2. Scan bars left to right with index i, keeping a stack of indices of increasing height.
  3. While the current bar is shorter than the bar on top, pop index top; its height is h = heights[top].
  4. Its rectangle spans from just after the new stack top to just before i: width is i if the stack is empty, else i - stack[-1] - 1. Update the best area with h * width.
  5. Push i and continue. Return the best area.

Python solution

PYTHON 3tested
def largest_rectangle_area(heights):
    best = 0
    stack = []                              # indices, heights increasing
    for i, h in enumerate(heights + [0]):   # sentinel 0 flushes the stack
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1   # last bar shorter than height
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

Complexity

TimeO(n)
SpaceO(n)

Each bar is pushed and popped exactly once, and each pop computes one rectangle in constant time.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(n) time because each bar is pushed and popped once, and O(n) space for the stack.

How does this help with Maximal Rectangle in a binary matrix?

Treat each row as the floor of a histogram where a column's height is the number of consecutive 1s above it. Run this algorithm on every row, for O(rows · cols) total.

Is there a divide-and-conquer solution?

Yes: the best rectangle either uses the shortest bar across the full width or lies entirely to its left or right. It averages O(n log n) but degrades to O(n²) on sorted input, so the stack is preferred.

Why do equal heights not break the algorithm?

With the strict comparison, an equal bar stays on the stack and the earlier one is measured later with the correct, wider span. The maximum area comes out right either way.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Stack & Monotonic Stack Stacks & the Monotonic Stack lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.