A Famous Problem

Given an array of bar heights representing a histogram, find the area of the largest rectangle that can be formed.

Example: heights $= [2, 1, 5, 6, 2, 3]$ Answer: $10$ (rectangle of height $5$ and width $2$ using bars at indices $2$ and $3$) You're solving a classic interview problem.

Brute force is $O(n^2)$. The monotonic stack solution is $O(n)$.