Largest Rectangle in Histogram
Learn Largest Rectangle in Histogram (Stack, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
The Problem Given bar heights of a histogram, find the area of the LARGEST rectangle that fits entirely within the bars. The brute force tries every pair of left/right boundaries - O(n²) or worse. A monotonic stack solves it in a single O(n) pass.