Largest Rectangle in Histogram

The key idea

For each bar, the widest rectangle using it as the shortest bar reaches left and right until it hits a strictly shorter bar. A monotonic-increasing stack of indices finds both of those boundaries in one left-to-right pass: when a shorter bar arrives, the popped bar's right boundary is the current index and its left boundary is the new stack top.

Problem

You are given an array of integers heights representing the heights of bars in a histogram, where each bar has a width of 1.

Return the area of the largest rectangle that can be formed within the bounds of the histogram. The rectangle must be made of whole bars standing side by side, so its height is limited by the shortest bar it spans.

Constraints

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

Examples

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

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

Complexity

Time: O(n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →