How do you find the largest rectangle in a histogram?

Q: How do you find the largest rectangle in a histogram?

**Target Audience:** Beginners preparing for coding interviews — no prior algorithms knowledge assumed **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First A city has a row of buildings of different heights, all one block wide and standing shoulder to shoulder. A billboard company wants to paint the **biggest possible rectangular advert** across their faces. The advert must be a single rectangle, it must sit on the ground, and it cannot stick out above any building it covers. A tall tower on its own gives a tall, thin advert; a long run of medium buildings gives a short, wide one. Which is bigger? You could try every pair of "first building" and "last b

The problem

Question presented to candidate: "You are given a list of bar heights for a histogram where every bar is 1 unit wide. Find the area of the largest rectangle that fits inside the bars. Start with any working idea, then get it to linear time. Please write it in Python."

What a strong answer should cover:

The rectangle's height is the shortest bar it covers, so each bar's best rectangle spans from its previous smaller bar to its next smaller bar.
A monotonic stack of indices (heights increasing) finds both edges at the moment a bar is popped; width is i - stack[-1] - 1 or i when the stack is empty.
O(n) time because each index is pushed and popped once; O(n) extra space for the stack; the O(n^2) brute force as a warm-up.
A sentinel height 0 at the end (or a final clean-up loop) so bars still on the stack are counted.
Python specifics: a plain list is the stack (append/pop/[-1]), stack[-1] on an empty list raises IndexError, and Python ints never overflow.

Clarifying questions expected:

"Can heights be 0, and can the list be empty?"
"Do you want only the area, or the bounds of the rectangle too?"

Code / implementation expected: Yes — largest_rectangle(heights) in Python with a list used as a stack, ideally in one pass with a sentinel.

dsa
monotonic-stack
arrays

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no prior algorithms knowledge assumed Difficulty: Hard Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

A city has a row of buildings of different heights, all one block wide and standing shoulder to shoulder. A billboard company wants to paint the biggest possible rectangular advert across their faces. The advert must be a single rectangle, it must sit on the ground, and it cannot stick out above any building it covers. A tall tower on its own gives a tall, thin advert; a long run of medium buildings

The solution is hidden so you can try first

12 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonThe monotonic stack on tricky inputs, with the winning rectangle

Practice

PythonBrute force versus stack, counting steps, plus a 64-bit area

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.