Solution: Largest Rectangle in a Histogram

Problem Statement

Given the bar heights of a histogram, return the area of the largest rectangle that fits inside it.

Examples

Example 1

• Input: heights = [2, 1, 5, 6, 2, 3]
• Expected Output: 10

Example 2

• Input: heights = [2, 4]
• Expected Output: 4

Example 3

• Input: heights = [5, 4, 3, 2, 1]
• Expected Output: 9

Turning the question around

Trying every pair of endpoints is O(n squared), and it is worth naming as the starting point. The way out is to stop asking about rectangles and start asking about bars:

For each ba