AlgoViz
HomeStack

Largest Rectangle in Histogram

Medium

Monotonic stack over the bar heights

Problem

Given histogram bar heights, return the area of the largest rectangle under it.

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

Maintain a stack of increasing heights; when a shorter bar arrives, every taller bar on the stack has found its right boundary and its rectangle can be measured. Each bar enters and leaves once, giving O(n).

The trick

  • Store indices, not heights, so widths can be computed.
  • Append a zero-height sentinel to close every remaining rectangle.
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.