Largest Rectangle in Histogram: Monotonic Stack

LeetCode's Largest Rectangle in Histogram (problem 84) is one of the classic hard problems that tests whether you truly understand monotonic stacks. It is rated hard, but the core idea builds directly on the same pop-when-smaller loop you use in Daily Temperatures and Next Greater Element. The difference is what you compute when you pop: instead of a distance to the next warmer day, you compute a rectangle area.

The problem

You are given an array of integers heights where each element represents the height of a bar in a histogram. Every bar has a width of 1. Return the area of the largest rectangle that can be formed within the histogram.

Input:  heights = [2, 1, 5, 6, 2, 3]
Output: 10

The largest rectangle is formed by bars at indices 2 and 3 (heights 5 and 6). The rectangle has height 5 (the shorter of the two) and width 2, giving area = 5 * 2 = 10.

The brute force

For every bar, you could expand left and right as far as possible while all bars in that range are at least as tall as the current bar. The width of that range times the current bar's height gives the largest rectangle using that bar as the shortest one.

def largest_rectangle_brute(heights):
    n = len(heights)
    max_area = 0
    for i in range(n):
        left = i
        right = i
        while left > 0 and heights[left - 1] >= heights[i]:
            left -= 1
        while right < n - 1 and heights[right + 1] >= heights[i]:
            right += 1
        max_area = max(max_area, heights[i] * (right - left + 1))
    return max_area

This is O(n^2) in the worst case. For a strictly increasing array, each bar expands all the way to the left, doing O(n) work per bar.

The key insight: monotonic increasing stack

Maintain a stack of bar indices in increasing order of height. When you encounter a bar that is shorter than the bar on top of the stack, the top bar can no longer extend to the right. Pop it and calculate the area it can form.

Here is why this works:

1. You push indices onto the stack as long as heights are non-decreasing. The stack stores bars that might still extend further to the right.
2. When you hit a bar shorter than the top, the top bar's rightward extension is blocked. Pop it. The width of the rectangle for that popped bar stretches from just after the new stack top to just before the current index.
3. After iterating through all bars, pop whatever remains on the stack. For each, the right boundary is the end of the array.

The width formula when you pop index p at position i is:

• If the stack is empty after popping: width = i (the popped bar can extend all the way to the left edge)
• If the stack is not empty: width = i - stack[-1] - 1 (from one past the new top to one before the current index)

Step-by-step walkthrough

Let's trace through heights = [2, 1, 5, 6, 2, 3]. The array is shown on the left with the current index highlighted. The stack is on the right. The running max_area appears below the array.

Key observations:

• The stack stays increasing. Every time you push, the new bar is at least as tall as what is on top. That is what makes it a monotonic increasing stack.
• Step 5 is where the magic happens. Bar 4 (height 2) is shorter than both bar 3 (height 6) and bar 2 (height 5), so both get popped. When bar 2 is popped, its width spans from index 2 to index 3 (two bars), giving area = 5 * 2 = 10.
• Each index is pushed once and popped once. Even though step 5 pops two elements, across the full run each bar enters and leaves the stack exactly once. That is the O(n) guarantee.
• The cleanup phase pops anything left. Bars that were never blocked to the right get resolved using the array length as the right boundary.

The code

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    n = len(heights)

    for i in range(n):
        while stack and heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)

    while stack:
        h = heights[stack.pop()]
        w = n if not stack else n - stack[-1] - 1
        max_area = max(max_area, h * w)

    return max_area

Breaking it down:

1. Walk through each bar left to right.
2. While the current bar is shorter than the top of the stack, pop the top. Compute the area using the popped bar's height and the width between the current index and the new stack top.
3. Push the current index.
4. After the loop, pop all remaining bars. For each, the right boundary is n (the end of the array).
5. The width calculation uses the same formula in both loops: if the stack is empty after popping, the bar extends the full width to the left.

Complexity analysis

Time: O(n). Each of the n indices is pushed onto the stack exactly once and popped at most once. The while loop does at most n pops total across all iterations. So the total work is O(n).

Space: O(n). In the worst case (a strictly increasing array like [1, 2, 3, 4, 5]), no bars get popped during the main loop. The stack holds all n elements until the cleanup phase.

You trade O(n) space for an order-of-magnitude time improvement. For arrays up to 100,000 elements (LeetCode's constraint), the stack solution runs comfortably within the time limit.

The building blocks

This problem is built on two reusable bricks:

Monotonic stack pop loop

The core pattern is the same one from Daily Temperatures and Next Greater Element:

while stack and compare(current, stack[-1]):
    popped = stack.pop()
    # process popped element
stack.append(current)

For this problem, the comparison is heights[i] < heights[stack[-1]] (pop when the current bar is shorter). For Daily Temperatures, it is temps[i] > temps[stack[-1]] (pop when the current temp is warmer). Same structure, flipped direction.

Area calculation with bounded width

When you pop an index, you need to compute the rectangle area. The height is heights[popped]. The width depends on how far that bar can extend:

w = i if not stack else i - stack[-1] - 1

If the stack is empty, nothing to the left is shorter, so the bar extends all the way to index 0. If the stack is not empty, the bar extends from one past the new top (stack[-1] + 1) to one before the current index (i - 1). This gives width i - stack[-1] - 1.

This width calculation is the piece that makes Largest Rectangle in Histogram harder than Daily Temperatures. In Daily Temperatures, you just subtract indices. Here, the width is bounded on both sides.

Edge cases

Before submitting, verify your solution handles:

• Single bar [5]: the answer is 5. One bar with height 5, width 1.
• All same height like [3, 3, 3, 3]: nothing gets popped during the main loop. The cleanup phase pops each bar with width stretching across the full array. Answer = 3 * 4 = 12.
• Strictly increasing like [1, 2, 3, 4]: nothing gets popped during the main loop. The cleanup phase handles everything. The largest rectangle is the one that spans the most bars at the minimum height. For this case, max(14, 23, 32, 41) = 6.
• Strictly decreasing like [4, 3, 2, 1]: every bar triggers a pop of the previous bar. The largest rectangle is again 41=4 or 32=6 or 23=6 or 14=4, so the answer is 6.
• Contains zeros like [2, 0, 2]: a bar of height 0 blocks any rectangle from crossing it. The answer is 2.

The monotonic stack solution handles all of these without special cases.

From understanding to recall

You have seen how the monotonic increasing stack processes bars left to right, popping when a shorter bar arrives and computing the rectangle area using the bounded width formula. The algorithm is elegant, but it has several moving parts: the comparison direction (pop on shorter, not taller), the two-phase structure (main loop plus cleanup), and the width calculation that depends on whether the stack is empty.

Under interview pressure, people commonly mix up the comparison direction (using > instead of <), forget the cleanup phase, or get the width formula wrong for the empty-stack case. These are not conceptual failures. They are recall failures.

Spaced repetition fixes this. Instead of solving the problem once and hoping you remember, you practice the pop loop and the width formula at increasing intervals. After a few reps, the code flows without hesitation, and you can focus your interview energy on explaining the approach rather than debugging syntax.

Related posts

• Daily Temperatures - The best introduction to monotonic stacks, using the same pop loop with a simpler computation (distance instead of area)
• Trapping Rain Water - Another histogram problem where you need to find bounding bars, solved optimally with two pointers

CodeBricks breaks the monotonic stack pattern into its reusable pieces and drills them individually. You type the pop loop and the width formula from scratch each time, building the muscle memory so that when you see Largest Rectangle in Histogram in an interview, the code flows without hesitation.