Largest rectangle in a histogram with a Python list

Why it matters

Many problems turn into a question about bars. A chart of daily sales is a row of bars. A grid of cells where some are free and some are blocked can be turned into one row of bars per line of the grid. Finding the largest rectangle inside a row of bars is the core step of several standard problems, including the largest square or rectangle of free cells in a grid.

A direct method checks every bar, extends a rectangle outward from it, and keeps the best area. That takes O(n squared) time for n bars in the worst case, which means doubling the number of bars makes the work about four times as large. The method in this lesson does the same job in O(n) time. It uses the monotonic stack from an earlier lesson of this module, with one new idea: the stack remembers, for each bar, how far the bar can stretch.

The earlier lessons of this module cover the stack itself and the first use of a monotonic stack. This lesson does not repeat them.

Words you will need

• Histogram: a row of bars, all with the same width, where each bar has a height. Here every bar has width 1, so the width of a rectangle is just the number of bars it covers.
• Rectangle: a block of bars that touches the base line. The rectangle's height is the lowest bar it covers, because a rectangle cannot stick out above a short bar.
• Area: width times height. The area of a rectangle is the number of unit squares it covers.
• Left limit and right limit: for one bar, the nearest bars on each side that stop its rectangle. The rectangle can reach up to the bar just before the left limit, and up to the bar just before the right limit.
• Index: the position of a bar in the row, counting from 0.
• Monotonic stack: a stack whose values always go one way from bottom to top. Here the heights increase from bottom to top.
• Sentinel: an extra value added at the end of a list so that the loop empties the stack. Here the sentinel is a bar of height 0.
• Pop and push: pop removes the top item of a stack and returns it. Push puts an item on top.

In Python, a plain list is used as the stack. stack.append(x) pushes x. stack.pop() removes the last item and returns it. stack[-1] reads the last item without removing it. In Python, -1 as an index means "counted from the end", so stack[-1] is always the top of a list used this way.

Start with the picture

Take six bars with heights 2, 1, 5, 6, 2 and 3. Here is the row, drawn from the top down. A # marks each unit of height of a bar.

|          #       |
|       #  #       |
|       #  #       |
|       #  #     # |
| #     #  #  #  # |
| #  #  #  #  #  # |

The bars are at indexes 0 to 5. The tallest bar, height 6, is at index 3. Which rectangle has the largest area? A rectangle using only the height-6 bar has area 6. A rectangle using the bars at indexes 2 and 3, both at least height 5, has width 2 and height 5, so its area is 10. No other rectangle is larger, so the answer is 10.

The answer is found by choosing a height, then looking at the widest run of bars that are at least that tall. The brute force method below does exactly that.

The brute force method

For each bar, take its height as the rectangle's height. Then grow the rectangle left and right, one bar at a time, for as long as the next bar is at least as tall. The width is the number of bars covered, and the area is the height times that width.

Here is the work for index 2, which has height 5. The bar to its left, at index 1, has height 1, which is less than 5, so the rectangle stops on the left at index 2. The bar to its right, at index 3, has height 6, which is at least 5, so the rectangle grows. The bar at index 4 has height 2, which is less than 5, so it stops there. The rectangle covers indexes 2 and 3, so the width is 2 and the area is 5 times 2, which is 10.

The method is simple and correct. Its cost is the problem. For each bar it may scan the whole row. Take the heights 1, 2, 3, 4, 5. For bar 0, the scan to the right covers all five bars. For bar 1, it covers four. Each bar extends right to the end, so the total is 5 + 4 + 3 + 2 + 1 = 15 steps. For n rising bars the total is about n squared divided by 2.

Keep the brute force method. It is the reference answer for checking the faster method, and the test later in this lesson uses it that way.

The key idea: each bar needs two numbers

Look at the rectangle for one bar, with height h. It covers a run of bars that are all at least h tall, and the run is as wide as possible. Its two ends are set by bars that are shorter than h. Call the index of the nearest shorter bar on the left the left limit, and the index of the nearest shorter bar on the right the right limit.

If you know both limits, the width is the right limit minus the left limit, minus 1. The bars strictly between the two limits are exactly the bars the rectangle covers. For the bar at index 2 in the example, the left limit is index 1 and the right limit is index 4. The width is 4 minus 1, minus 1, which is 2.

So the whole problem reduces to finding both limits for every bar, quickly. A monotonic stack does that in one pass.

The stack method

Walk through the bars from left to right. The stack holds the indexes of bars that are still waiting for a shorter bar to appear on their right. Because a bar stays on the stack only while no shorter bar has come after it, the heights on the stack increase from the bottom to the top.

For the current bar at index i with height cur, do these steps.

1. While the stack is not empty and the bar on top has height at least cur, pop it. Call it top. The current bar is the first bar to the right of top that is not taller than top, so the current index is the right limit of top.
2. After the pop, the bar now on top of the stack, if there is one, is the left limit of top. If the stack is empty, the left limit is -1, meaning the rectangle can reach the left edge.
3. The width of top's rectangle is i minus the left limit, minus 1. Its area is the height of top times that width. Keep the largest area seen so far.
4. When no more bars are popped, push i onto the stack.

After the last real bar, add a sentinel step at index n with height 0. No bar is shorter than 0, so at this step the loop pops every bar still on the stack. Without the sentinel, the bars still on the stack at the end would never get an area computed, and the answer could be too small.

Here is the reason the left limit in step 2 is correct. Suppose the bar just below top on the stack is at index L. Any bar between L and top in the row was pushed after L and then removed before top was pushed. A bar that is removed is removed by a bar that is at least as short as it. So if any bar between L and top were shorter than top, the chain of removals would have to end in a bar that is still on the stack below top, and no such bar exists between L and top. So every bar between L and top is at least as tall as top, and L is the nearest shorter bar on the left.

The right limit is correct for a similar reason. The current bar is the first bar on the right that is no taller than top, because otherwise top would have been popped earlier.

Worked example 1: trace [2, 1, 5, 6, 2, 3]

The table below follows the algorithm on the six bars and the sentinel. Each row is one step. The pops column lists each popped bar with its height, width and area. The stack column is written from bottom to top.

Look at index 4. The height 2 pops bar 3, which has height 6. The bar below it, bar 2, is still on the stack, so the width of bar 3 is 4 minus 2, minus 1, which is 1. Then the height 2 pops bar 2, which has height 5. The bar below it on the stack is bar 1, so bar 2's left limit is index 1. Its width is 4 minus 1, minus 1, which is 2, and its area is 10. This is the rectangle found by hand earlier.

The sentinel at index 6 pops three bars. The largest area is 10, which matches the brute force answer.

Here is the real output of a Python program that prints this trace. The program is listed in full in the full program section below.

Heights [2, 1, 5, 6, 2, 3]
Brute force: 10
Stack trace (indexes, bottom to top):
i=0 cur=2 pops: none  stack after [0]
i=1 cur=1 pops: bar0(h=2,w=1,area=2)  stack after [1]
i=2 cur=5 pops: none  stack after [1, 2]
i=3 cur=6 pops: none  stack after [1, 2, 3]
i=4 cur=2 pops: bar3(h=6,w=1,area=6) bar2(h=5,w=2,area=10)  stack after [1, 4]
i=5 cur=3 pops: none  stack after [1, 4, 5]
i=6 cur=0 pops: bar5(h=3,w=1,area=3) bar4(h=2,w=4,area=8) bar1(h=1,w=6,area=6)  stack after []
Stack answer: 10

The full program

The program below has the brute force method, the stack method, a check of the two against each other on 5000 random rows, and a count of pushes and pops for a long row. The counters are only there to support the proof later in the lesson. The if __name__ == "__main__": line means the code under it runs only when the file is run directly, not when another file imports it.

The output of the program is below. The trace lines are the same as in the table. The other lines come from the other checks.

Heights [2, 1, 5, 6, 2, 3]
Brute force: 10
Stack trace (indexes, bottom to top):
i=0 cur=2 pops: none  stack after [0]
i=1 cur=1 pops: bar0(h=2,w=1,area=2)  stack after [1]
i=2 cur=5 pops: none  stack after [1, 2]
i=3 cur=6 pops: none  stack after [1, 2, 3]
i=4 cur=2 pops: bar3(h=6,w=1,area=6) bar2(h=5,w=2,area=10)  stack after [1, 4]
i=5 cur=3 pops: none  stack after [1, 4, 5]
i=6 cur=0 pops: bar5(h=3,w=1,area=3) bar4(h=2,w=4,area=8) bar1(h=1,w=6,area=6)  stack after []
Stack answer: 10
[6, 2, 5, 4, 5, 1, 6] brute=12 stack=12
[1, 2, 3, 4, 5] brute=9 stack=9
[3, 3, 3, 3] brute=12 stack=12
[0] brute=0 stack=0
[] brute=0 stack=0
random cases: 5000, mismatches: 0
rising, n=100000: answer 2500050000, pushes 100000, pops 100000
area: 10000000000

The random check compares the two methods on 5000 rows with 0 to 12 bars, each height between 0 and 5. It found no difference. A check like this does not prove the method is right, but it catches most mistakes in the details, such as an off-by-one width, quickly. The random rows come from a seeded generator, so the same numbers appear on every run.

Worked example 2: a harder row with a tie

Take the row 6, 2, 5, 4, 5, 1, 6. The best rectangle covers indexes 2, 3 and 4, with heights 5, 4 and 5. Its lowest bar is 4, its width is 3, and its area is 12. Check the alternatives. The single bar at index 0 has area 6. The bars at indexes 1 to 4 have lowest height 2 and width 4, so area 8. The brute force and the stack method both give 12.

Worked example 3 shows what happens with equal heights. Take the row 3, 3, 3, 3. The method pops with >=, so a bar equal in height to the current one is popped too. Index 1 pops index 0 and gets width 1, area 3. Index 2 pops index 1. Nothing is below index 1 on the stack, so its left limit is -1 and its width is 2, area 6. Index 3 pops index 2 with width 3, area 9. The sentinel pops index 3 with width 4, area 12, which is the answer. Here is the real trace.

i=0 cur=3 pops: none  stack after [0]
i=1 cur=3 pops: bar0(h=3,w=1,area=3)  stack after [1]
i=2 cur=3 pops: bar1(h=3,w=2,area=6)  stack after [2]
i=3 cur=3 pops: bar2(h=3,w=3,area=9)  stack after [3]
i=4 cur=0 pops: bar3(h=3,w=4,area=12)  stack after []

The tie rule is safe. Take two equal bars, with height 3, at indexes 1 and 3. Their rectangles have the same left limit, because neither bar is shorter than the other. The right limit of the first bar is the second bar, since the second bar is no taller. So the first bar's rectangle is a part of the second bar's rectangle. Stopping the first one early loses nothing.

The last example is the smallest case. The row [0] has one bar of height 0, so the answer is 0. The empty row has no bars, so the answer is also 0. The sentinel step still runs with i equal to 0 when the row is empty, and the loop does nothing that changes the answer.

Why each bar is popped once

The stack method is O(n) because each bar goes onto the stack once and comes off once. Here is the argument in plain steps.

1. Each bar is pushed exactly once, at its own step. It is pushed only when i is less than n, so the sentinel is never pushed. That makes n pushes for a row of n bars.
2. A pop removes a bar from the stack for good. The bar is never pushed again, because each bar is pushed only at its own step.
3. So the total number of pops is at most the number of pushes, which is n.
4. Each step of the outer loop does one failed check, which is the test "stack not empty and top height at least cur" coming out false, or the stack being empty. That is at most one check for each of the n + 1 steps.
5. Each pop does a fixed amount of work: one comparison, one subtraction and one multiplication.

So the total work is at most about 2n + 1 steps of fixed size, which is O(n). The rising row of 100000 bars in the program shows the count. Every bar is pushed, and every bar is popped, so the pops equal 100000, the number of bars. At the sentinel step, every bar left on the stack has height at least 0, so the loop pops them all.

What Python does differently

Python lists have no peek method. stack[-1] does the job of Java's peek. The difference is what happens on an empty list. stack[-1] raises an error, where Java's Deque.peek would return null. The code above checks if stack before it reads the top, for that reason.

Python integers have no fixed size. An int grows to fit the number, so the area of a tall, wide row needs no special type. The product 100000 times 100000 is printed exactly, as the program output shows. Fixed-size integers, such as a 32-bit int in C or Java, wrap around when the result is too large. Python does not do this for its own int type. Some libraries that work with arrays of numbers do use fixed-size integers, and those can wrap around.

Common mistakes

Forgetting the sentinel. Without the final step at index n, the bars still on the stack at the end never get an area. Take the row 1, 2, 3. The correct answer is 4, from the two bars of height 2 and 3 with width 2. A version that skips the sentinel prints this:

no sentinel 0 correct 4

The answer is 0 because nothing is ever popped. Always run one more step with height 0 after the last bar.

Writing the width as i - left instead of i - left - 1. The width is the number of bars strictly between the two limits. The left limit is excluded, and so is the current bar. A version that forgets the - 1 counts one bar too many on each rectangle. On the example row it prints this:

wrong width 15 correct 10

The check that catches it is the brute force comparison. Run one small example by hand as well. A row with one bar of height 4 has width 1 for that bar. The sentinel at index 1 pops it with left limit -1, so the wrong formula gives 1 - (-1), which is 2, and the area would be 8 instead of 4.

Storing heights on the stack instead of indexes. The width needs the position of the left limit, not its height. A stack of heights cannot give the width, so the method fails. Store the index of each bar and read its height from the list when needed.

Reading the top of an empty stack. When the stack is empty, stack[-1] raises an error. The message is:

IndexError: list index out of range

Calling peek fails in a different way, because a Python list has no such method:

AttributeError: 'list' object has no attribute 'peek'

The fix is to check if stack first, as the program does with left = stack[-1] if stack else -1.

Forgetting to push the current bar. The loop pops bars that are too tall for the current bar, and then it must push the current bar, so that later bars can find it as a left limit. Skip the push and the bar never reaches the stack, so nothing ever pops it and it never gets an area. On the row [4] the answer is 0 instead of 4:

no push 0 correct 4

Practice

Exercise 1: find the answer by hand

Find the largest rectangle for the row 3, 1, 3, 2, 2. Name the bars that make it.

Show the answer

The best rectangle covers bars at indexes 2, 3 and 4, with heights 3, 2 and 2. Its lowest bar is 2, its width is 3, and its area is 6. The single bar at index 0 has area 3, and the bar at index 2 alone has area 3. The answer is 6. Running the brute and largest functions from the program on this row gives 6 from both.

Exercise 2: left and right limits

For the row 2, 1, 5, 6, 2, 3, give the left limit and the right limit of each bar. Use the nearest strictly shorter bar on the left, and the nearest bar on the right that is shorter than or equal in height. Use -1 for no left limit and 6 for no right limit.

Show the answer

Left limits: [-1, -1, 1, 2, 1, 4]. Right limits: [1, 6, 4, 4, 6, 6]. For example, the bar at index 2 has height 5, its nearest shorter bar on the left is at index 1, and its nearest shorter-or-equal bar on the right is at index 4. Its width is 4 minus 1, minus 1, which is 2. The widths and areas follow from these lists, and the largest area is 10, from the bar at index 2.

Exercise 3: count the pushes and pops

For the row 5, 4, 3, 2, 1, how many pushes and how many pops happen with the stack method, and what is the answer?

Show the answer

There are 5 pushes, one for each bar, and 5 pops. Each bar is popped by the next, shorter bar, and the sentinel pops the last one. The answer is 9. The bar at index 0 has height 5, and the bar at index 1 has height 4. The best rectangle covers the first three bars, with lowest height 3, which gives an area of 9.

Exercise 4: a row of equal bars

What is the answer for the row 2, 2, 2? Explain which pop gives it.

Show the answer

The answer is 6. The rectangle covers all three bars at height 2. The stack method finds it at the sentinel step. When the sentinel with height 0 arrives, the stack holds only index 2, and nothing is below it, so its left limit is -1 and its width is 3. Its area is 2 times 3, which is 6. The earlier pops at steps 1 and 2 give areas of 2 and 4, which are smaller.

Exercise 5: the area of a tall row

A row has 3 bars, each of height 2000000000. What area does the Python program compute for the whole row, and why is no special integer type needed?

Show the answer

The area is 6000000000, which is 2000000000 times 3. A Python int has no fixed size, so the product is exact. A 32-bit integer has a largest value of 2147483647, so a 32-bit area would wrap around and give a wrong number. Python does not wrap around for its own int type.

Summary

• The largest rectangle for each bar is set by its nearest shorter bar on each side, and the width between those two limits gives its area.
• A monotonic stack of indexes finds both limits in one pass. A pop tells you the right limit of the popped bar, and the bar left below it on the stack is its left limit.
• A sentinel bar of height 0 at the end empties the stack, so every bar gets an area.
• Each bar is pushed once and popped at most once, so the method takes O(n) time.
• Check the stack method against a brute force method on small random rows.