Builds on Next Greater Element, which you haven’t finished yet.
Monotonic Stack (Largest Rectangle in Histogram)
You're given an array of integers heights, each entry the height of one histogram bar; every bar has width 1. Return the area of the largest rectangle you can draw that fits entirely inside the histogram's outline.
Histogram Stack
histogram heights ➔ stack maintains left/right boundaries ➔ width * height area| 1 | def largest_rectangle_area(heights: list[int]) -> int: |
| 2 | """Largest Rectangle in Histogram with virtual 0-sentinel flush. |
| 3 | Time: O(N) | Space: O(N) |
| 4 | """ |
| 5 | # stack holds bar indices above the -1 left-boundary sentinel, with heights strictly increasing from bottom to top |
| 6 | extended_heights = heights + [0] # Virtual sentinel flushes stack at the end! |
| 7 | stack = [-1] # Left boundary sentinel |
| 8 | max_area = 0 |
| 9 | |
| 10 | # 1. Sweep Bars Left To Right, Including The Sentinel: |
| 11 | # The appended 0 guarantees that by the end of this loop, every real bar has been popped and measured, so no cleanup pass is needed after it. |
| 12 | for i, h in enumerate(extended_heights): |
| 13 | # 2. Resolve Every Bar At Least As Tall As The Incoming One: |
| 14 | # Bar h is shorter than the popped bar, so the popped bar's rectangle cannot reach past i on the right, and the new stack top is the nearest shorter bar on its left; that fixes both edges, so its widest rectangle is now known. |
| 15 | while stack[-1] != -1 and extended_heights[stack[-1]] >= h: |
| 16 | popped_height = extended_heights[stack.pop()] |
| 17 | width = i - stack[-1] - 1 |
| 18 | max_area = max(max_area, popped_height * width) |
| 19 | |
| 20 | # 3. Push The Current Bar As Still Unresolved: |
| 21 | # Bar i survived every pop above, so it becomes the newest bar waiting for a shorter bar on its right to fix its own width. |
| 22 | stack.append(i) |
| 23 | |
| 24 | # 4. Return The Largest Rectangle Found: |
| 25 | # Every bar was pushed once and popped at most once, and the sentinel guarantees every bar was measured, so max_area already holds the largest rectangle. |
| 26 | return max_area |
-1, the heights at the indices in stack strictly increase from bottom to top, so each index sits right above the nearest lower bar to its left.Keep stack as bar indices with increasing heights, and when a lower bar h arrives, pop every bar at least as tall: that bar's widest rectangle is now known. It cannot extend to i, where a lower bar stands, or to the new stack[-1], the nearest lower bar on its left, so its width is i - stack[-1] - 1. The trap is measuring that width before the pop, or from the popped index itself: the left edge is the new top after the pop, which is why stack starts with -1 for bars that reach the left edge. The 0 appended in extended_heights pops every bar that is left, so no cleanup loop is needed after the scan.
See it run
Histogram Stack, step by step
stack [-1]max_area 0
The top row is the heights with the added 0 at the end. The column number is the bar index. The bottom row is the stack: the left cell is the bottom, each cell holds a bar index or -1, and a blank cell is an unused slot.
hthe bar being read nowsentinelthe 0 added after the last barpoppedthe bar taken off the stack, whose rectangle is measured nowleft wallthe new top after the pop, the nearest lower bar on the leftpushedthe bar index that was just pushed
Start: stack holds only -1, the left edge, and max_area is 0. A 0 is added after the last bar.
Gotcha 1 of 5
- The trap
Gotcha 1: Measuring
widthbefore the popMistakewidth = i - stack[-1] - 1 popped_height = extended_heights[stack.pop()]Fixpopped_height = extended_heights[stack.pop()] width = i - stack[-1] - 1What happens: The popped bar's rectangle ends at the nearest lower bar on each side. On the right that bar is
i. On the left it is the new top ofstack, after the pop. Before the pop,stack[-1]is the popped bar itself. The width then leaves out the popped bar itself and the taller bars on its left.Example: heights = [2, 1, 5, 6, 2, 3]Mistake: returns 5Fix: returns 10
- The area is set by two chosen lines and the distance between them, and the lines in between don't limit it, as in Container With Most Water (LC 11). See Converging Pointers
- You must add up a value over every subarray instead of finding one best rectangle, as in Sum of Subarray Ranges (LC 2104). See Contribution Technique
Deep Dive
What a pop adds: the width of the popped bar
In Monotonic Stack (Next Greater Element), a pop only records an answer for the popped item. In Largest Rectangle in Histogram (LC 84), a pop must also measure how far the popped bar reaches to the left and to the right.
The bar at the popped index p is the lowest bar of its rectangle. The rectangle extends right until a bar that is not taller, and left until a bar that is lower. The first bar that is not taller on the right is the bar i that causes the pop. The bar under p in stack is the nearest lower bar on the left.
So both walls are known at the moment of the pop. The bars strictly between them are all at least as tall as the popped bar, and the width is i - stack[-1] - 1. The area is popped_height * width.
A bar between p and i that was popped earlier was popped by a bar taller than p. A bar that was not taller would have popped p first. This is why no short bar hides inside the rectangle.
Example: for heights = [2, 1, 5, 6, 2, 3], the largest rectangle has height 5 and width 2. It covers bars 2 and 3, and its area is 10.
One trace: measure each bar at the moment it is popped
The board replays heights = [2, 1, 5, 6, 2, 3] with the added 0 at the end. The bottom row is stack, and its first cell holds the left edge -1.
Bar 1 (height 1) pops bar 0 (height 2). The new top is -1, so width = 1 - (-1) - 1 = 1 and the area is 2. Bars 2 and 3 are pushed, because they are taller than the top.
Bar 4 (height 2) pops bar 3 (height 6). The new top is bar 2, so width = 4 - 2 - 1 = 1 and the area is 6. Then it pops bar 2 (height 5). The new top is bar 1, so width = 4 - 1 - 1 = 2 and the area is 10. That is the answer.
The added 0 pops the rest: bar 5 has area 3, bar 4 has area 8 (width 4), and bar 1 has area 6 (width 6). None is larger than 10.
Why -1 starts the stack and 0 ends the heights
stack = [-1] is the left edge. A bar with no lower bar on its left reaches index 0. When it is popped, the top is -1, so width = i - (-1) - 1 = i. The condition stack[-1] != -1 keeps -1 from ever being popped. If stack started empty, stack[-1] would raise IndexError on the first read.
extended_heights = heights + [0] is the right edge. Bars that are still on stack when the real bars end have no lower bar on their right. The added 0 is lower than or equal to every bar, so it pops all of them, and each one is measured with i = len(heights). No cleanup loop is needed after the scan.
Build the new list with heights + [0]. Calling heights.append(0) changes the list of the caller. After the call, the caller finds an extra 0 at the end of its own data.
The cost, and why two pointers do not work here
The cost is O(N) time and O(N) space. Every bar, including the added 0, is pushed once and popped at most once.
Trapping Rain Water (LC 42) can use two pointers. The water above a bar depends on the tallest bar on its left and the tallest bar on its right. If max_left < max_right, the left side sets the level, whatever lies between. So the pointer on the shorter side can move in safely, and the space is O(1).
Largest Rectangle in Histogram (LC 84) has no such rule. A bar is limited by the nearest lower bar on each side, and not by the tallest bar. Those walls are local, and a pointer at an end of the array cannot see them.
Example: for heights = [2, 1, 5, 6, 2, 3], put one pointer at index 0 (height 2) and one at index 5 (height 3). The best rectangle is bars 2 and 3 with height 5 and area 10. It sits inside the array. Neither pointer says which side to move to reach it, because bar 1 (height 1) limits every rectangle that starts at an end.
The stack finds each bar's two walls in one scan. That is why it is the right tool here.
The two cards use the same scan with opposite stack orders. Trapping Rain Water (LC 42) keeps heights that never increase, and a taller bar closes a valley. This card keeps heights that strictly increase, and a lower bar closes a rectangle.
Rain water is added layer by layer, from the popped floor up to the lower wall. A rectangle is measured once, for the popped bar, across the full width between its two walls.
The trap: read the width after the pop, and use popped_height
Write popped_height = extended_heights[stack.pop()] first. Then write width = i - stack[-1] - 1. Before the pop, stack[-1] is the popped bar itself, so the width leaves out the popped bar and the taller bars next to it. For [2, 1, 5, 6, 2, 3] the wrong order gives 5 and not 10.
Multiply by popped_height, not by h. h is the lower bar that caused the pop. For [2, 1], using h gives 1, and the correct answer is 2.
The pop uses >=, so a bar of equal height is popped too. That cuts the popped bar's rectangle at i, but the equal bar at i stays on stack and later measures a rectangle that reaches back over the same bars. For [2, 2] the second bar gives 2 * 2 = 4.
60-Second Pitch
"The best rectangle has a lowest bar, so I measure each bar as the lowest bar of its own rectangle. I keep a stack of bar indexes whose heights strictly increase. When a lower bar arrives, I pop every bar that is at least as tall. For a popped bar, the right wall is the incoming bar and the left wall is the new top, so the width is the incoming index minus the new top minus 1. I start the stack with -1 as the left edge, and I add a 0 height at the end so that every bar is popped and measured. Each bar is pushed once and popped at most once, so the time is O(N) and the space is O(N)."
Common Questions
- What does this card add on top of Monotonic Stack (Next Greater Element)?
The pop does more. Next Greater Element only records an answer for the popped item. Here the popped bar also needs its left wall, which is the next item in
stack. So the width is known at the moment of the pop, and the area is measured there.- Can I use two pointers, like in Trapping Rain Water (LC 42)?
No. In Trapping Rain Water (LC 42) the water level comes from the tallest bar on each side, so the shorter side tells you which pointer to move. Here each bar is limited by the nearest lower bar on each side. Pointers at the ends cannot find those bars, and the best rectangle can sit inside the array. Use the stack.
- Why do you need the extra 0 at the end?
Bars still on
stackwhen the loop ends have no lower bar on their right. The added 0 is lower than every bar, so it pops all of them, and each one gets measured. Without it you need a second loop after the scan to measure the bars that remain.- Why is the width
i - stack[-1] - 1? iis the right wall andstack[-1]is the left wall, after the pop. Both walls are lower bars that are not part of the rectangle. The bars strictly between them are the rectangle, and there arei - stack[-1] - 1of them.- What happens when two bars have the same height?
The pop uses
>=, so the earlier bar is popped when the equal bar arrives. Its rectangle is measured short. The equal bar stays onstackand later measures a rectangle that includes the earlier bar's cells. The largest area is still found.
SWE Reasoning
Spot it
- The answer is the best rectangle or range whose value is set by its lowest element: height times width, or minimum times length.
- For each element you need how far it can extend to the left and to the right before a lower element stops it.
- Trying every pair of bars and taking the minimum between them is O(N^2) time or worse.
- A next-greater-style scan fits, but each pop also needs the left boundary.
- Bars of height 0 or equal heights can appear, so the tie rule must be clear.
The invariant, step by step
stackstarts as[-1]. Above the-1, the heights at the indexes instackstrictly increase from bottom to top.- Bar
ihas heighth. While the top bar has height at leasth, it is popped. - The popped bar cannot extend to
ior past it. The newstack[-1]is a lower bar on its left, and it cannot extend to that bar either. - So
width = i - stack[-1] - 1, and the rectangle with heightpopped_heightis measured.max_areakeeps the largest one. - When the top is lower than
h, popping stops, and bariis pushed. The heights onstackstill strictly increase. - The added 0 at the end pops every real bar. Each one has been measured when the scan ends.
Traps
widthread before the pop. The top is still the popped bar. Readpopped_heightand pop first, then computewidth.h * width.his the bar that caused the pop. Usepopped_height.stack = []. A bar that reaches the left edge needs a left wall. Start with[-1].heights.append(0). It changes the caller's list. Useheights + [0].- Pushing
h. The width needs the position of a bar. Pushi.
Practice
Builds on Next Greater Element, which you haven’t finished yet.
Monotonic Stack (Largest Rectangle in Histogram)
You're given an array of integers heights, each entry the height of one histogram bar; every bar has width 1. Return the area of the largest rectangle you can draw that fits entirely inside the histogram's outline.
Histogram Stack
histogram heights ➔ stack maintains left/right boundaries ➔ width * height area| 1 | def largest_rectangle_area(heights: list[int]) -> int: |
| 2 | """Largest Rectangle in Histogram with virtual 0-sentinel flush. |
| 3 | Time: O(N) | Space: O(N) |
| 4 | """ |
| 5 | # stack holds bar indices above the -1 left-boundary sentinel, with heights strictly increasing from bottom to top |
| 6 | extended_heights = heights + [0] # Virtual sentinel flushes stack at the end! |
| 7 | stack = [-1] # Left boundary sentinel |
| 8 | max_area = 0 |
| 9 | |
| 10 | # 1. Sweep Bars Left To Right, Including The Sentinel: |
| 11 | # The appended 0 guarantees that by the end of this loop, every real bar has been popped and measured, so no cleanup pass is needed after it. |
| 12 | for i, h in enumerate(extended_heights): |
| 13 | # 2. Resolve Every Bar At Least As Tall As The Incoming One: |
| 14 | # Bar h is shorter than the popped bar, so the popped bar's rectangle cannot reach past i on the right, and the new stack top is the nearest shorter bar on its left; that fixes both edges, so its widest rectangle is now known. |
| 15 | while stack[-1] != -1 and extended_heights[stack[-1]] >= h: |
| 16 | popped_height = extended_heights[stack.pop()] |
| 17 | width = i - stack[-1] - 1 |
| 18 | max_area = max(max_area, popped_height * width) |
| 19 | |
| 20 | # 3. Push The Current Bar As Still Unresolved: |
| 21 | # Bar i survived every pop above, so it becomes the newest bar waiting for a shorter bar on its right to fix its own width. |
| 22 | stack.append(i) |
| 23 | |
| 24 | # 4. Return The Largest Rectangle Found: |
| 25 | # Every bar was pushed once and popped at most once, and the sentinel guarantees every bar was measured, so max_area already holds the largest rectangle. |
| 26 | return max_area |
-1, the heights at the indices in stack strictly increase from bottom to top, so each index sits right above the nearest lower bar to its left.Keep stack as bar indices with increasing heights, and when a lower bar h arrives, pop every bar at least as tall: that bar's widest rectangle is now known. It cannot extend to i, where a lower bar stands, or to the new stack[-1], the nearest lower bar on its left, so its width is i - stack[-1] - 1. The trap is measuring that width before the pop, or from the popped index itself: the left edge is the new top after the pop, which is why stack starts with -1 for bars that reach the left edge. The 0 appended in extended_heights pops every bar that is left, so no cleanup loop is needed after the scan.
See it run
Histogram Stack, step by step
stack [-1]max_area 0
The top row is the heights with the added 0 at the end. The column number is the bar index. The bottom row is the stack: the left cell is the bottom, each cell holds a bar index or -1, and a blank cell is an unused slot.
hthe bar being read nowsentinelthe 0 added after the last barpoppedthe bar taken off the stack, whose rectangle is measured nowleft wallthe new top after the pop, the nearest lower bar on the leftpushedthe bar index that was just pushed
Start: stack holds only -1, the left edge, and max_area is 0. A 0 is added after the last bar.
Gotcha 1 of 5
- The trap
Gotcha 1: Measuring
widthbefore the popMistakewidth = i - stack[-1] - 1 popped_height = extended_heights[stack.pop()]Fixpopped_height = extended_heights[stack.pop()] width = i - stack[-1] - 1What happens: The popped bar's rectangle ends at the nearest lower bar on each side. On the right that bar is
i. On the left it is the new top ofstack, after the pop. Before the pop,stack[-1]is the popped bar itself. The width then leaves out the popped bar itself and the taller bars on its left.Example: heights = [2, 1, 5, 6, 2, 3]Mistake: returns 5Fix: returns 10
- The area is set by two chosen lines and the distance between them, and the lines in between don't limit it, as in Container With Most Water (LC 11). See Converging Pointers
- You must add up a value over every subarray instead of finding one best rectangle, as in Sum of Subarray Ranges (LC 2104). See Contribution Technique
Deep Dive
What a pop adds: the width of the popped bar
In Monotonic Stack (Next Greater Element), a pop only records an answer for the popped item. In Largest Rectangle in Histogram (LC 84), a pop must also measure how far the popped bar reaches to the left and to the right.
The bar at the popped index p is the lowest bar of its rectangle. The rectangle extends right until a bar that is not taller, and left until a bar that is lower. The first bar that is not taller on the right is the bar i that causes the pop. The bar under p in stack is the nearest lower bar on the left.
So both walls are known at the moment of the pop. The bars strictly between them are all at least as tall as the popped bar, and the width is i - stack[-1] - 1. The area is popped_height * width.
A bar between p and i that was popped earlier was popped by a bar taller than p. A bar that was not taller would have popped p first. This is why no short bar hides inside the rectangle.
Example: for heights = [2, 1, 5, 6, 2, 3], the largest rectangle has height 5 and width 2. It covers bars 2 and 3, and its area is 10.
One trace: measure each bar at the moment it is popped
The board replays heights = [2, 1, 5, 6, 2, 3] with the added 0 at the end. The bottom row is stack, and its first cell holds the left edge -1.
Bar 1 (height 1) pops bar 0 (height 2). The new top is -1, so width = 1 - (-1) - 1 = 1 and the area is 2. Bars 2 and 3 are pushed, because they are taller than the top.
Bar 4 (height 2) pops bar 3 (height 6). The new top is bar 2, so width = 4 - 2 - 1 = 1 and the area is 6. Then it pops bar 2 (height 5). The new top is bar 1, so width = 4 - 1 - 1 = 2 and the area is 10. That is the answer.
The added 0 pops the rest: bar 5 has area 3, bar 4 has area 8 (width 4), and bar 1 has area 6 (width 6). None is larger than 10.
Why -1 starts the stack and 0 ends the heights
stack = [-1] is the left edge. A bar with no lower bar on its left reaches index 0. When it is popped, the top is -1, so width = i - (-1) - 1 = i. The condition stack[-1] != -1 keeps -1 from ever being popped. If stack started empty, stack[-1] would raise IndexError on the first read.
extended_heights = heights + [0] is the right edge. Bars that are still on stack when the real bars end have no lower bar on their right. The added 0 is lower than or equal to every bar, so it pops all of them, and each one is measured with i = len(heights). No cleanup loop is needed after the scan.
Build the new list with heights + [0]. Calling heights.append(0) changes the list of the caller. After the call, the caller finds an extra 0 at the end of its own data.
The cost, and why two pointers do not work here
The cost is O(N) time and O(N) space. Every bar, including the added 0, is pushed once and popped at most once.
Trapping Rain Water (LC 42) can use two pointers. The water above a bar depends on the tallest bar on its left and the tallest bar on its right. If max_left < max_right, the left side sets the level, whatever lies between. So the pointer on the shorter side can move in safely, and the space is O(1).
Largest Rectangle in Histogram (LC 84) has no such rule. A bar is limited by the nearest lower bar on each side, and not by the tallest bar. Those walls are local, and a pointer at an end of the array cannot see them.
Example: for heights = [2, 1, 5, 6, 2, 3], put one pointer at index 0 (height 2) and one at index 5 (height 3). The best rectangle is bars 2 and 3 with height 5 and area 10. It sits inside the array. Neither pointer says which side to move to reach it, because bar 1 (height 1) limits every rectangle that starts at an end.
The stack finds each bar's two walls in one scan. That is why it is the right tool here.
The two cards use the same scan with opposite stack orders. Trapping Rain Water (LC 42) keeps heights that never increase, and a taller bar closes a valley. This card keeps heights that strictly increase, and a lower bar closes a rectangle.
Rain water is added layer by layer, from the popped floor up to the lower wall. A rectangle is measured once, for the popped bar, across the full width between its two walls.
The trap: read the width after the pop, and use popped_height
Write popped_height = extended_heights[stack.pop()] first. Then write width = i - stack[-1] - 1. Before the pop, stack[-1] is the popped bar itself, so the width leaves out the popped bar and the taller bars next to it. For [2, 1, 5, 6, 2, 3] the wrong order gives 5 and not 10.
Multiply by popped_height, not by h. h is the lower bar that caused the pop. For [2, 1], using h gives 1, and the correct answer is 2.
The pop uses >=, so a bar of equal height is popped too. That cuts the popped bar's rectangle at i, but the equal bar at i stays on stack and later measures a rectangle that reaches back over the same bars. For [2, 2] the second bar gives 2 * 2 = 4.
60-Second Pitch
"The best rectangle has a lowest bar, so I measure each bar as the lowest bar of its own rectangle. I keep a stack of bar indexes whose heights strictly increase. When a lower bar arrives, I pop every bar that is at least as tall. For a popped bar, the right wall is the incoming bar and the left wall is the new top, so the width is the incoming index minus the new top minus 1. I start the stack with -1 as the left edge, and I add a 0 height at the end so that every bar is popped and measured. Each bar is pushed once and popped at most once, so the time is O(N) and the space is O(N)."
Common Questions
- What does this card add on top of Monotonic Stack (Next Greater Element)?
The pop does more. Next Greater Element only records an answer for the popped item. Here the popped bar also needs its left wall, which is the next item in
stack. So the width is known at the moment of the pop, and the area is measured there.- Can I use two pointers, like in Trapping Rain Water (LC 42)?
No. In Trapping Rain Water (LC 42) the water level comes from the tallest bar on each side, so the shorter side tells you which pointer to move. Here each bar is limited by the nearest lower bar on each side. Pointers at the ends cannot find those bars, and the best rectangle can sit inside the array. Use the stack.
- Why do you need the extra 0 at the end?
Bars still on
stackwhen the loop ends have no lower bar on their right. The added 0 is lower than every bar, so it pops all of them, and each one gets measured. Without it you need a second loop after the scan to measure the bars that remain.- Why is the width
i - stack[-1] - 1? iis the right wall andstack[-1]is the left wall, after the pop. Both walls are lower bars that are not part of the rectangle. The bars strictly between them are the rectangle, and there arei - stack[-1] - 1of them.- What happens when two bars have the same height?
The pop uses
>=, so the earlier bar is popped when the equal bar arrives. Its rectangle is measured short. The equal bar stays onstackand later measures a rectangle that includes the earlier bar's cells. The largest area is still found.
SWE Reasoning
Spot it
- The answer is the best rectangle or range whose value is set by its lowest element: height times width, or minimum times length.
- For each element you need how far it can extend to the left and to the right before a lower element stops it.
- Trying every pair of bars and taking the minimum between them is O(N^2) time or worse.
- A next-greater-style scan fits, but each pop also needs the left boundary.
- Bars of height 0 or equal heights can appear, so the tie rule must be clear.
The invariant, step by step
stackstarts as[-1]. Above the-1, the heights at the indexes instackstrictly increase from bottom to top.- Bar
ihas heighth. While the top bar has height at leasth, it is popped. - The popped bar cannot extend to
ior past it. The newstack[-1]is a lower bar on its left, and it cannot extend to that bar either. - So
width = i - stack[-1] - 1, and the rectangle with heightpopped_heightis measured.max_areakeeps the largest one. - When the top is lower than
h, popping stops, and bariis pushed. The heights onstackstill strictly increase. - The added 0 at the end pops every real bar. Each one has been measured when the scan ends.
Traps
widthread before the pop. The top is still the popped bar. Readpopped_heightand pop first, then computewidth.h * width.his the bar that caused the pop. Usepopped_height.stack = []. A bar that reaches the left edge needs a left wall. Start with[-1].heights.append(0). It changes the caller's list. Useheights + [0].- Pushing
h. The width needs the position of a bar. Pushi.