DSA Tracker

Visualize

Largest Rectangle in Histogram

Monotonic increasing stack of indices

time O(n)space O(n)

Every rectangle is capped by its own shortest bar, so ask of each bar: how far left and right can it stretch before something shorter blocks it? Scanning left to right, a bar's right edge is decided the moment a shorter bar appears — and until then the bar is still open. A stack holding indices in increasing height order remembers exactly the open bars, and because it is sorted, whatever sits below a popped bar is the first shorter bar to its LEFT. So one pop hands you both edges at once, each bar is pushed and popped once, and the whole thing runs in a single O(n) pass.

Details

Animated on: heights = [2, 1, 5, 6, 2, 3] — find the largest rectangle that fits entirely inside the histogram.

Problem:Largest Rectangle in HistogramHard

Pattern:Monotonic Stack

Monotonic increasing stack of indices

step 1 / 14

2
[0]
1
[1]
5
[2]
6
[3]
2
[4]
3
[5]
0
[6]

Bars 2, 1, 5, 6, 2, 3, plus an appended 0-height bar at index 6 so every real bar is forced off the stack and measured. The stack keeps indices whose heights only ever increase.

  • i=0· arr[0] = 2
Pseudocode
1FUNCTION largestRectangle(H):
2  APPEND 0 TO H
3  stack <- [-1]
4  best <- 0
5  FOR i <- 0 TO LENGTH(H) - 1:
6    WHILE TOP(stack) != -1 AND H[TOP(stack)] > H[i]:
7      top <- POP(stack)
8      width <- i - TOP(stack) - 1
9      best <- MAX(best, H[top] * width)
10    PUSH i ONTO stack
11  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. Bars 2, 1, 5, 6, 2, 3, plus an appended 0-height bar at index 6 so every real bar is forced off the stack and measured. The stack keeps indices whose heights only ever increase.
  2. Nothing on the stack is taller than height 2, so bar 0 might still extend rightwards — push it and move on. Stack now holds [0], heights 2 climbing left to right.
  3. Bar 1 is height 1, shorter than bar 0's height 2, so bar 0 can never grow any wider to the right — pop and measure it now. Its rectangle stretches from index 0 to 0, width 1, area 2 x 1 = 2, the best so far.
  4. Nothing on the stack is taller than height 1, so bar 1 might still extend rightwards — push it and move on. Stack now holds [1], heights 1 climbing left to right.
  5. Nothing on the stack is taller than height 5, so bar 2 might still extend rightwards — push it and move on. Stack now holds [1, 2], heights 1 < 5 climbing left to right.
  6. Nothing on the stack is taller than height 6, so bar 3 might still extend rightwards — push it and move on. Stack now holds [1, 2, 3], heights 1 < 5 < 6 climbing left to right.
  7. Bar 4 is height 2, shorter than bar 3's height 6, so bar 3 can never grow any wider to the right — pop and measure it now. Its rectangle stretches from index 3 to 3, width 1, area 6 x 1 = 6, the best so far.
  8. Bar 4 is height 2, shorter than bar 2's height 5, so bar 2 can never grow any wider to the right — pop and measure it now. Its rectangle stretches from index 2 to 3, width 2, area 5 x 2 = 10, the best so far.
  9. Nothing on the stack is taller than height 2, so bar 4 might still extend rightwards — push it and move on. Stack now holds [1, 4], heights 1 < 2 climbing left to right.
  10. Nothing on the stack is taller than height 3, so bar 5 might still extend rightwards — push it and move on. Stack now holds [1, 4, 5], heights 1 < 2 < 3 climbing left to right.
  11. Bar 6 is height 0, shorter than bar 5's height 3, so bar 5 can never grow any wider to the right — pop and measure it now. Its rectangle stretches from index 5 to 5, width 1, area 3 x 1 = 3, which loses to the best of 10.
  12. Bar 6 is height 0, shorter than bar 4's height 2, so bar 4 can never grow any wider to the right — pop and measure it now. Its rectangle stretches from index 2 to 5, width 4, area 2 x 4 = 8, which loses to the best of 10.
  13. Bar 6 is height 0, shorter than bar 1's height 1, so bar 1 can never grow any wider to the right — pop and measure it now. Its rectangle stretches from index 0 to 5, width 6, area 1 x 6 = 6, which loses to the best of 10.
  14. Every bar has been popped exactly once, so every candidate rectangle was measured. The winner spans indices 2..3 at the shorter of those heights: area 10.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Largest Rectangle in Histogram in the editorAll Stack problemsBack to roadmap