AlgoViz
HomeStack

Largest rectangle in a histogram

Hard

Each bar's rectangle spans to the smaller neighbours

Problem

Given bar heights, find the area of the largest rectangle that fits under the histogram.

In simple words

For each bar, use a stack to find how far it can stretch left and right while staying the shortest.

The idea

For each bar the widest rectangle at its height reaches to the previous and next strictly smaller bars. A monotonic increasing stack finds both boundaries in one sweep, so the whole problem is O(n) rather than O(n²).

The trick

  • When popping, the current index is the right boundary and the new stack top is the left one.
  • Width = right - left - 1, using indices rather than counts.
  • A sentinel of height 0 at the end flushes the stack cleanly.
2
1
5
6
2
3
0
1
2
3
4
5

Step 1 of 8. Brute force: treat each bar as the shortest, stretch out while neighbours are tall enough. Values: 2, 1, 5, 6, 2, 3.

1/8
Brute force
timeO(n²)spaceO(1)

Expand from each bar.

1// each bar as the shortest, expand both sides2for (let i = 0; i < n; i++) {3  let l = i; while (l > 0 && h[l - 1] >= h[i]) l--;4  let r = i; while (r < n - 1 && h[r + 1] >= h[i]) r++;5  best = Math.max(best, h[i] * (r - l + 1));6}

Input

array
[2, 1, 5, 6, 2, 3]

Memory

i
—

Output

best
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
heights = [2, 1, 5, 6, 2, 3]
Output:
10
Explanation:
The 5,6 bars form a 10-area rectangle.

Example 2

Input:
heights = [2, 4]
Output:
4
Explanation:
Best rectangle has area 4.

Example 3

Input:
heights = [2, 1, 2]
Output:
3
Explanation:
The full width at height 1 → area 3.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.