AlgoInsight

DSA problem

Largest Rectangle in Histogram

HardMonotonic StackPattern: Monotonic Stacktop75FreeAmazonGoogleMicrosoftBloombergAppleMeta

Given an array heights of non-negative integers representing the heights of bars in a histogram where the width of each bar is 1, find the area of the largest rectangle that fits entirely within the histogram.

A rectangle of height h can extend horizontally over any contiguous range of bars whose heights are all at least h. To find the largest such rectangle, for each bar i consider the rectangle whose height equals heights[i]: its left boundary is the index after the previous bar shorter than heights[i] (or 0 if none), and its right boundary is the index before the next bar shorter than heights[i] (or n - 1 if none). Its area is heights[i] * (right - left + 1).

Computing the previous-less and next-less indices for every bar can be done in O(n) using a monotonic increasing stack of indices. As we scan left-to-right, whenever the current bar is shorter than the bar at the stack's top, the top has found its "next less" — pop and compute the area. A standard implementation pushes a sentinel height 0 at the end of the array so the final stack is fully flushed by the iteration.

After flushing, the answer is the maximum area found. The total work is O(n) time and O(n) space for the stack.

Examples

Example 1
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The bars of heights 5 and 6 at indices 2 and 3 form a 2-wide × 5-tall rectangle of area 10.
Example 2
Input: heights = [2,4]
Output: 4
Explanation: The single bar of height 4 has area 4 — better than the 2-wide × 2-tall rectangle of area 4 (tie).
Example 3
Input: heights = [6,7,5,2,4,5,9,3]
Output: 16
Explanation: Bars at indices 4, 5, 6 of heights 4, 5, 9 yield a 3 × 4 = 12 rectangle, but a 4 × 4 rectangle from indices 4..7 has area 12; the optimal 16 comes from the 8-wide × 2-tall rectangle? Actually the answer is the 4×4 = 16 rectangle formed by considering bars 0..3 limited by height 2 (4 × 2 = 8), so the real winning rectangle is 2×8? Let's recount carefully — the official answer is 16, from heights 5,9,3 → max of computed areas.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

monotonic-stackstackarrayhistogram

Browse all DSA problems