Skip to content
Get started

Biggest rectangle under a skyline

A histogram has 10 bars of width 1 with heights

3, 5, 2, 6, 6, 4, 7, 1, 5, 4.

What is the area of the largest axis-aligned rectangle that fits entirely under the bars?

Show hints (2)+
  1. The best rectangle is as tall as some bar and stretches until a shorter bar blocks it.
  2. A stack of increasing heights gives each bar's nearest shorter neighbour on both sides.

Answer

Reveal answer →

16

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions