hard

Largest Rectangle in Histogram

Given bar heights of a histogram with unit-width bars, find the area of the largest axis-aligned rectangle that fits entirely inside the histogram.

Constraints
  • 1 ≤ n ≤ 10^5
  • 0 ≤ heights[i] ≤ 10^4
Examples
in: heights = [2,1,5,6,2,3]
out: 10
Bars 5 and 6 form a 2 × 5 rectangle.

Code it yourself

Solve in
Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.
Hints:
Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.