Largest rectangle in a histogram

Why this matters

A histogram is a row of bars, where each bar has a height. The question is: what is the largest rectangle you can fit under the bars, if the rectangle sits on the same baseline as the bars? The rectangle can be as wide as several bars, but it cannot be taller than the shortest bar it covers.

This question shows up in several places. A program that reads a scanned table may need the largest solid block of filled cells. A program that plans a warehouse may need the largest free rectangular area between shelves. A grid of 0s and 1s can be turned into a histogram row by row, which makes this problem the base of a harder one, shown in the examples below.

A direct method checks many pairs of bars and takes a long time for large inputs. This lesson uses a monotonic stack, the same tool from the lesson Next greater element and the monotonic stack, to solve the problem in one pass. The work grows in a straight line with the number of bars. The lesson also proves that each bar is popped from the stack exactly once, which is the reason the method is fast.

The problem, with a picture in words

Take the heights {2, 1, 5, 6, 2, 3}. There are six bars, numbered 0 to 5 from the left. Bar 0 has height 2, bar 1 has height 1, and so on.

A rectangle covers a run of neighbouring bars. Its height is the height of the shortest bar in that run, because a taller rectangle would stick out above that short bar. Its width is the number of bars in the run. Its area is height times width.

Look at bars 2 and 3, with heights 5 and 6. The shortest of the two is 5, and the width is 2. The area is 10. No other rectangle here is larger, so the answer is 10.

The brute force method tries every run of bars. It is easy to write, and it is a good way to check a faster method.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
 
long long brute(const std::vector<int>& heights) {
    long long best = 0;
    const std::size_t n = heights.size();
    for (std::size_t l = 0; l < n; ++l) {
        int lowest = heights[l];
        for (std::size_t r = l; r < n; ++r) {
            lowest = std::min(lowest, heights[r]);
            best = std::max(best, static_cast<long long>(lowest) * static_cast<long long>(r - l + 1));
        }
    }
    return best;
}
 
int main() {
    std::cout << brute({2, 1, 5, 6, 2, 3}) << '\n';
}

Output:

10

This code has two nested loops, so it does about n squared divided by 2 steps for n bars. For 100,000 bars that is about five billion steps. The monotonic stack method needs about 100,000 steps for the same input.

The key idea: every rectangle has a shortest bar

Pick any rectangle that is as large as it can be. Its height comes from one bar inside it, and that bar is the shortest bar in the rectangle. Call it bar t. The rectangle cannot grow to the left or to the right past a bar shorter than t, because the shorter bar would cut its height.

So if you know two things for bar t, you know its best rectangle:

• The left limit is the index of the nearest bar to the left that is shorter than t. If there is none, use -1.
• The right limit is the index of the nearest bar to the right that is shorter than t. If there is none, use the number of bars.

The width of the rectangle is the right limit minus the left limit minus 1, because the bars strictly between the two limits are the ones the rectangle covers. The area is height of t times that width. The answer is the largest of these areas over all bars.

Take bar 2 in {2, 1, 5, 6, 2, 3}. Its height is 5. The nearest shorter bar on the left is bar 1 (height 1), so the left limit is 1. The nearest shorter bar on the right is bar 4 (height 2), so the right limit is 4. The width is 4 - 1 - 1 = 2. The area is 5 times 2, which is 10.

The task is now to find the left limit and the right limit for every bar quickly. A monotonic stack does this in one pass.

An everyday picture: walking out from a bar

Stand on top of one bar in the row. Walk left, one bar at a time, until you meet a bar shorter than yours. Stop there. Then walk right, the same way. The distance between the two stopping points, minus the bars at the stops, is how far your rectangle can stretch at your height.

Doing this walk for every bar separately is slow, because the walks overlap. The stack lets the walks share their work. It holds the bars whose right limit is still unknown, arranged from shortest at the bottom to tallest at the top. Each new bar either finishes some waiting bars or joins the waiting line.

The stack rule

The stack holds indexes, not heights. An index tells you where the bar is, and you need that position to compute widths. The heights are read from the array when needed.

The stack is kept strictly increasing in height from bottom to top. A new bar i with height h is handled like this:

1. While the stack is not empty and the bar on top has height greater than or equal to h, pop the top bar. Call it t. Its right limit is i, because bar i is the first bar to the right that is at most as tall as t. Its left limit is the bar now on top of the stack, or -1 if the stack is empty. Compute the area of t with that width and remember the largest area.
2. Push i onto the stack.

After the last real bar, add one extra bar of height 0 at position n. This bar is shorter than every real bar, so it pops everything that is still waiting. Real bars are never negative, so the extra 0 never causes a wrong answer.

Why is the stack increasing from bottom to top? When bar i arrives, every bar above a remaining bar t is taller than t, because the stack was increasing. Step 1 removes every bar at least as tall as h. What is left on top is shorter than h, and i goes on top of it. So the increasing rule holds after every step.

Worked trace, step by step

Here is the full run on {2, 1, 5, 6, 2, 3}. The extra bar of height 0 at the end is at index 6. The table shows the pops and the stack after each step. The stack is written bottom to top, as index(height).

Read step 4 closely, because it is where the answer 10 comes from. Bar 4 has height 2. Bar 3 (height 6) is on top and is at least 2, so it is popped. Its left limit is bar 2, which is now on top, and its right limit is 4. The width is 4 - 2 - 1 = 1, so its area is 6. Bar 2 (height 5) is on top next and is also at least 2, so it is popped too. Its left limit is bar 1, and its right limit is 4. The width is 4 - 1 - 1 = 2, and the area is 10. Bar 1 has height 1, which is less than 2, so the loop stops and bar 4 is pushed.

Every area in the table matches the left-limit and right-limit idea. For bar 4 (height 2), popped at step 6, the left limit is 1 and the right limit is 6, so the width is 4 and the area is 8. The largest area in the table is 10, and the program returns 10.

The code

The function below is the complete solution. It uses std::stack<int>, the standard container for a last-in, first-out stack. It needs only push, top, pop and empty.

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
 
long long largest_rectangle(const std::vector<int>& heights) {
    const int n = static_cast<int>(heights.size());
    std::stack<int> waiting;  // indexes; heights rise from bottom to top
    long long best = 0;
    for (int i = 0; i <= n; ++i) {
        const int h = (i == n) ? 0 : heights[i];  // the extra 0 empties the stack
        while (!waiting.empty() && heights[waiting.top()] >= h) {
            const int bar = waiting.top();
            waiting.pop();
            const int left = waiting.empty() ? -1 : waiting.top();
            const int width = i - left - 1;
            best = std::max(best, static_cast<long long>(heights[bar]) * width);
        }
        if (i < n) {
            waiting.push(i);
        }
    }
    return best;
}
 
int main() {
    std::cout << largest_rectangle({2, 1, 5, 6, 2, 3}) << '\n';
}

Output:

10

The long long type is used for the area. Section "Common mistakes" shows what happens with a 32-bit int.

The loop runs from i = 0 to i = n. At i = n the height is 0, and the if (i < n) check stops the extra bar from being pushed, because there is no real bar at index n to refer to.

Why each bar is popped exactly once

This is the proof the lesson promised. It has two parts: a counting argument for the speed, and a correctness argument for the answer.

The counting argument

Look at what happens to each index in the stack.

1. An index is pushed onto the stack only once. The loop pushes index i at step i, and each step pushes at most one index. So over the whole run there are exactly n pushes, one for each real bar.
2. An index leaves the stack only by being popped. Once popped, it never goes back on the stack, because the only push is the one at its own step.
3. The extra bar of height 0 at step n pops everything that is left, because every real bar is at least 0. So when the run ends, the stack is empty.

Put these together. Each of the n indexes is pushed once, and each leaves by a pop, so each is popped exactly once. There are exactly n pops in total.

Now count the work. The outer loop runs n + 1 times, and each run does a fixed amount of work plus its pops. The pops add up to n, so the total work is about n + 1 plus n, which is a straight line in n. The notation for this is O(n). A pop costs the same no matter how many bars are waiting, because it touches only the top of the stack.

The trace confirms the count. The six bars 0 to 5 are popped once each: bar 0 at step 1, bar 3 at step 4, bar 2 at step 4, bar 5 at step 6, bar 4 at step 6, bar 1 at step 6. That is six pops for six bars.

The correctness argument

The method is correct if the largest area it computes is the largest area of any rectangle. Here is why. Take the best rectangle, and let bar t be its shortest bar. Its extent is exactly the range from bar t's left limit to its right limit, because it cannot grow past a shorter bar. So its area is one of the areas the loop computes, provided the loop computes the correct limits for t. The next two claims show it does.

Claim one: the right limit is correct. Bar t stays on the stack from its own step until the step when it is popped, call that step i. Take any bar j strictly between t and i. Bar j did not pop t, because t was still on the stack when step j ran. The bars above t are always taller than t. If j were at most as tall as t, step j would pop everything above t, then t, which did not happen. So every bar between t and i is taller than t, and bar i is at most as tall as t. Bar i is the right limit in the sense used here.

Claim two: the left limit is correct. When bar t is pushed at its own step, the pops at that step leave the bar below it on top of the stack. Call that bar L. Suppose some bar in the gap between L and t is shorter than t. Pick the one closest to t, and call it m. Every bar between m and t is at least as tall as t, which is taller than m. None of those bars can pop m, because a bar pops only bars at least as tall as itself. So m is still on the stack, above L. The pops at the step for t stop at m, because m is shorter than t. So m, not L, would be left on top. That contradicts the choice of L. So no bar in the gap is shorter than t, and L is the correct left limit. While t sits on the stack, the bar below it does not change, so the left limit stays correct until t is popped.

With both limits correct, the width and area for each bar are correct, and the largest of them is the answer.

Equal heights

The stack pops bars whose height is equal to the new bar's height, not only taller ones. That means an equal bar can end a rectangle early. Consider {2, 2}. Bar 0 is popped by bar 1, which has the same height, so bar 0's rectangle is counted as width 1. Then bar 1 is popped by the extra 0, with left limit -1, so its width is 2 and its area is 4. The full rectangle is found through the second bar, because the second bar inherits the left limit of the first. The random tests below include many equal heights, and they all agree with the brute force method.

Random tests

The lesson's code was checked against the brute force method on 20,000 random lists. Each list has between 0 and 12 bars with heights from 0 to 6, so equal heights are common. The check uses a fixed random seed, so the result can be repeated:

failures 0 of 20000

A test like this does not prove the method, but it catches most mistakes in the limits and the width formula.

Worked examples

Example 1: the trace above

The trace table for {2, 1, 5, 6, 2, 3} is the first example. A copy of the same loop with a print statement added at each pop and each push gives this output. The printing lines are left out of the solution above.

i=0 h=2
   stack (bottom to top): 0(2)
i=1 h=1
   pop bar 0 height 2 left -1 right 1 width 1 area 2
   stack (bottom to top): 1(1)
i=2 h=5
   stack (bottom to top): 1(1) 2(5)
i=3 h=6
   stack (bottom to top): 1(1) 2(5) 3(6)
i=4 h=2
   pop bar 3 height 6 left 2 right 4 width 1 area 6
   pop bar 2 height 5 left 1 right 4 width 2 area 10
   stack (bottom to top): 1(1) 4(2)
i=5 h=3
   stack (bottom to top): 1(1) 4(2) 5(3)
i=6 h=0
   pop bar 5 height 3 left 4 right 6 width 1 area 3
   pop bar 4 height 2 left 1 right 6 width 4 area 8
   pop bar 1 height 1 left -1 right 6 width 6 area 6
   stack (bottom to top):
best 10

The stack is empty at the end, as the counting argument says it must be.

Example 2: small inputs with equal and rising bars

These inputs test the edges: two bars, three equal bars, an empty list, and a rising staircase.

std::cout << largest_rectangle({2, 4}) << ' '
          << largest_rectangle({3, 3, 3}) << ' '
          << largest_rectangle({}) << ' '
          << largest_rectangle({1, 2, 3, 4, 5}) << '\n';

Output:

4 9 0 9

For {2, 4}, the answer 4 comes from the bar of height 4 alone, or from both bars at height 2. For {3, 3, 3}, the whole row at height 3 gives 3 times 3 = 9. The empty list has no bars, so the answer is 0. For {1, 2, 3, 4, 5}, the last three bars at height 3 give 3 times 3 = 9. The height 2 rectangle over four bars gives 8, which is less.

Notice that an empty list needs no special code. The loop runs once with i = 0 = n, the extra 0 is the only bar, and nothing is popped.

Example 3: the largest rectangle of 1s in a grid

A grid of 0s and 1s can hold a rectangle of 1s. The idea is to treat each row as the baseline of a histogram. For each column, count how many 1s are stacked in a row going up from that row. That count is the bar height. Then apply the histogram method to the row.

Take this grid, where 1 means a filled cell:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Look at the third row, the last one with a full set of ones above it. The column heights are the count of 1s going up from that row:

• Column 0: 3 ones (rows 0, 1, 2).
• Column 1: 1 one (row 2 only), because row 1 has a 0 in that column.
• Column 2: 3 ones.
• Column 3: 2 ones (rows 1 and 2).
• Column 4: 2 ones (rows 1 and 2).

The histogram is {3, 1, 3, 2, 2}. The best rectangle is height 2 over columns 2 to 4, which has width 3 and area 6. The code keeps a height for each column and updates it row by row.

long long maximal_rectangle(const std::vector<std::vector<int>>& grid) {
    if (grid.empty()) return 0;
    std::vector<int> heights(grid[0].size(), 0);
    long long best = 0;
    for (const auto& row : grid) {
        for (std::size_t j = 0; j < row.size(); ++j) {
            heights[j] = row[j] == 1 ? heights[j] + 1 : 0;
        }
        best = std::max(best, largest_rectangle(heights));
    }
    return best;
}

The largest_rectangle function from the solution is used unchanged. For the grid above, the program prints:

6

The block of ones is rows 1 and 2, columns 2 to 4, which is 2 rows by 3 columns. The method runs one histogram per row, so the total work is about the number of cells in the grid.

Common mistakes

Forgetting the extra bar at the end

If the loop stops at n - 1, bars that are still on the stack when the input ends are never popped, so their areas are never counted. The output for an increasing list shows the problem. without_flush is the same method with the loop stopped at n - 1, so the extra bar is never added:

long long without_flush(const std::vector<int>& heights) {
    const int n = static_cast<int>(heights.size());
    std::stack<int> waiting;
    long long best = 0;
    for (int i = 0; i < n; ++i) {
        const int h = heights[i];
        while (!waiting.empty() && heights[waiting.top()] >= h) {
            const int bar = waiting.top();
            waiting.pop();
            const int left = waiting.empty() ? -1 : waiting.top();
            const int width = i - left - 1;
            best = std::max(best, static_cast<long long>(heights[bar]) * width);
        }
        waiting.push(i);
    }
    return best;
}

Called next to the correct function for {1, 2, 3}:

std::cout << without_flush({1, 2, 3}) << ' ' << largest_rectangle({1, 2, 3}) << '\n';

0 4

The first number is 0, which is wrong. The correct answer is 4, from the last two bars (heights 2 and 3) at height 2 over a width of 2. The second number is the fixed version's result.

Using the wrong width formula

The width is the right limit minus the left limit minus 1. Leaving out the minus 1 makes every width too large by one. Take the trace above, with bar 2 popped at i = 4. Its left limit is 1. The correct width is 4 - 1 - 1 = 2. The wrong formula i - left gives 3, so the area would be 15 instead of 10. This small test uses i = 4 and left = 1 and prints both formulas:

int i = 4;
int left = 1;
std::cout << "i-left " << i - left << " i-left-1 " << i - left - 1 << '\n';

i-left 3 i-left-1 2

When a width looks off by one, count the bars by hand. The bars strictly between the limits are the ones the rectangle covers, and their count is the width.

Storing heights instead of indexes

The stack must hold positions. If it holds only heights, the code cannot tell where the bar is, so it cannot find the left limit from the bar below it, and it cannot compute the width. A height of 2 could be at any position. Keep the index, and read the height from the array when needed.

Using a 32-bit int for the area

A bar of height 50,000 and width 50,000 has area 2,500,000,000. That is larger than the largest 32-bit int, which is about 2.1 billion. Signed overflow is undefined behaviour in C++. On this machine the product wraps to a negative number, and g++ with -Wall -Wextra gives no warning for this code. This small program computes the same product both ways:

#include <cstdio>
 
int main() {
    int height = 50000;
    int width = 50000;
    int area = height * width;
    long long wide = static_cast<long long>(height) * width;
    std::printf("int %d long long %lld\n", area, wide);
}

int -1794967296 long long 2500000000

The first value is the product computed in int, which overflowed. The second is the product computed in long long, which is correct. The solution uses long long for the area, so it is safe for large heights.

Confusing the two limits

The left limit is found from the stack below the popped bar. The right limit is the index of the bar that caused the pop. A common error is to use the bar's own index as one of the limits, or to swap them. A quick check is the example bar 2 above: its left limit is 1 and its right limit is 4, so the width is 2, which the trace confirms.

Practice

Exercise 1

Find the largest rectangle for {4, 2, 3} by hand. Then run the stack method on it, writing down each pop.

Show the answer

The rectangles are: height 4 over one bar gives 4; height 2 over all three bars gives 6; height 3 over one bar gives 3. The answer is 6.

The stack method: step 0 pushes index 0 (height 4). Step 1 (height 2) pops index 0, width 1, area 4, then pushes index 1. Step 2 (height 3) pushes index 2, because 2 is less than 3. Step 3 is the extra 0, which pops index 2 (width 1, area 3) then index 1 (left -1, right 3, width 3, area 6). The best is 6.

Exercise 2

Why does the algorithm compute the area when it pops a bar, and not when it pushes the bar?

Show the answer

When a bar is pushed, its right limit is not known yet, because the bars to its right have not been read. The right limit is found later, by the bar that pops it. At pop time both limits are known: the bar that causes the pop gives the right limit, and the bar left on top of the stack gives the left limit. So the area can be computed exactly at that moment.

Exercise 3

For {0, 0, 0}, what is the answer? What does the stack do at each step?

Show the answer

The answer is 0, because every rectangle has height 0. At step 0 the stack pushes index 0. At step 1 the height 0 is at least 0, so bar 0 is popped, with area 0, and bar 1 is pushed. The same happens at steps 2 and 3. The extra 0 at step 3 pops bar 2. Every pop computes area 0, so the best stays 0.

Exercise 4

For {6, 6, 6, 1}, what is the answer? Name the bar that gives it.

Show the answer

The answer is 18. It comes from the three bars of height 6, which form a rectangle of width 3 and height 6. Step 1 pops bar 0 (width 1, area 6), and step 2 pops bar 1 (nothing is left below it, so its left limit is -1, and its width is 2, area 12). Step 3 has height 1, so it pops bar 2 with left limit -1 and right limit 3. Its width is 3, and its area is 6 times 3 = 18. The brute force method gives the same value, 18.

Exercise 5

For the heights {2, 1, 5, 6, 2, 3}, write the left limit and the right limit of every bar. Use -1 for no left limit and 6 for no right limit. Then compute each bar's area.

Show the answer

Left limits: [-1, -1, 1, 2, 1, 4]. Right limits: [1, 6, 4, 4, 6, 6].

The widths are right limit minus left limit minus 1: 1, 6, 2, 1, 4, 1. The areas are height times width: 2, 6, 10, 6, 8, 3. The largest is 10, which matches the trace. Each area in this list also appears in the pop column of the trace table.

Summary

• The largest rectangle has a shortest bar, and its width is set by the nearest shorter bars on each side.
• A monotonic stack of indexes finds each bar's left limit and right limit in one pass.
• A bar is popped when a shorter or equal bar arrives, and its area is computed at that moment, with both limits known.
• An extra bar of height 0 at the end empties the stack, so every bar's area is counted.
• Each index is pushed once and popped once, so the total work is a straight line in the number of bars.
• A grid of 0s and 1s can be solved by applying this method to each row, with column heights counted from the row above.