Largest Rectangle in Histogram: the monotonic stack as a boundary oracle

Pick any bar at index i. If you want to draw the tallest possible rectangle that uses that bar's full height, you need to know how far left and how far right you can extend before hitting a shorter bar. The moment you hit a bar shorter than heights[i], that bar cannot be part of a rectangle of height heights[i] — so you stop. The rectangle's width is determined by those two boundaries. Its area is heights[i] * width.

That framing turns "largest rectangle" into "for each bar, find its left and right shorter-bar boundaries." Everything else is just choosing how efficiently you find those boundaries.

The constraints push hard on efficiency. 1 <= heights.length <= 10^5 and 0 <= heights[i] <= 10^4. A hundred thousand bars. If finding boundaries takes O(n) per bar, you are at O(n²) total — around 10^10 operations in the worst case, which will time out. The constraints are telling you O(n) or at worst O(n log n) is required. That is not a hint; it is a directive.

The problem

Given an array of integers heights where each element represents the height of a histogram bar of width 1, return the area of the largest rectangle that can be formed within the histogram. Full statement: LeetCode 84.

Constraints:
- 1 <= heights.length <= 10^5
- 0 <= heights[i] <= 10^4

Brute force: scan for boundaries on every bar

The brute force is direct. For each bar i, walk left until you find a bar shorter than heights[i], walk right until you find the same, compute the area, track the maximum.

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        max_area = 0
 
        for i in range(n):
            # Walk left to find the first bar shorter than heights[i]
            left = i
            while left > 0 and heights[left - 1] >= heights[i]:
                left -= 1
 
            # Walk right to find the first bar shorter than heights[i]
            right = i
            while right < n - 1 and heights[right + 1] >= heights[i]:
                right += 1
 
            width = right - left + 1
            max_area = max(max_area, heights[i] * width)
 
        return max_area

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int n = heights.Length;
        int maxArea = 0;
 
        for (int i = 0; i < n; i++) {
            int left = i;
            while (left > 0 && heights[left - 1] >= heights[i])
                left--;
 
            int right = i;
            while (right < n - 1 && heights[right + 1] >= heights[i])
                right++;
 
            int width = right - left + 1;
            maxArea = Math.Max(maxArea, heights[i] * width);
        }
 
        return maxArea;
    }
}

This is correct. For a strictly decreasing input like [5, 4, 3, 2, 1], bar 0 (height 5) walks right four steps, bar 1 (height 4) walks right three, and so on — the total work is n + (n-1) + ... + 1 = O(n²). The inner loops are not constant; they are proportional to how far the boundary lies.

Time: O(n²). Space: O(1). It passes for small inputs. It will not pass for n = 10^5.

The monotonic stack: O(n) by making each bar enter and leave exactly once

The key insight: the brute force re-computes boundaries from scratch for every bar. The redundancy is massive — when bar i walks left and finds its boundary, it is often redoing work that bar i-1 already did.

The monotonic stack eliminates this by processing boundaries lazily. Instead of searching for a bar's right boundary when you visit it, you discover that boundary later — when a shorter bar arrives and tells all the taller bars behind it "your reign is over."

Here is the invariant: the stack always holds bar indices in increasing order of height (bottom to top). When bar i arrives:

• If heights[i] is at least as tall as the stack top, it extends that existing right boundary, so push i.
• If heights[i] is shorter, it is the right boundary for every bar taller than it at the top of the stack. Pop each such bar, compute its area with i as the right limit, then push i.

After the main loop, bars still in the stack can all extend to the right edge of the array — process them with n as the right limit.

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []   # indices, maintained in increasing height order
        max_area = 0
        n = len(heights)
 
        for i in range(n):
            while stack and heights[i] < heights[stack[-1]]:
                height = heights[stack.pop()]
                # Left boundary: the new stack top (exclusive), or index 0 if stack is empty
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
 
        # Remaining bars extend to the right edge
        while stack:
            height = heights[stack.pop()]
            width = n if not stack else n - stack[-1] - 1
            max_area = max(max_area, height * width)
 
        return max_area

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        var stack = new Stack<int>();
        int maxArea = 0;
        int n = heights.Length;
 
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && heights[i] < heights[stack.Peek()]) {
                int height = heights[stack.Pop()];
                int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
                maxArea = Math.Max(maxArea, height * width);
            }
            stack.Push(i);
        }
 
        while (stack.Count > 0) {
            int height = heights[stack.Pop()];
            int width = stack.Count == 0 ? n : n - stack.Peek() - 1;
            maxArea = Math.Max(maxArea, height * width);
        }
 
        return maxArea;
    }
}

The width formula deserves a close reading. When you pop bar j:

• Its right boundary is i (the bar that triggered the pop), exclusive.
• Its left boundary is stack[-1] + 1 after the pop (the new top), exclusive. If the stack is empty after popping, there is nothing shorter to the left of j, so the left boundary is index 0 — and width = i - 0 = i.

So: width = i - stack[-1] - 1 when the stack is non-empty, and width = i when it is empty.

Step-by-step trace: heights = [2, 1, 5, 6, 2, 3]

i=0, h=2:  stack=[], push 0        -> stack=[0]
i=1, h=1:  h < heights[0]=2, pop 0
             height=2, stack=[], width=1, area=2*1=2
           push 1                  -> stack=[1]
i=2, h=5:  h > heights[1]=1, push 2 -> stack=[1,2]
i=3, h=6:  h > heights[2]=5, push 3 -> stack=[1,2,3]
i=4, h=2:  h < heights[3]=6, pop 3
             height=6, stack=[1,2], width=4-2-1=1, area=6*1=6
           h < heights[2]=5, pop 2
             height=5, stack=[1], width=4-1-1=2, area=5*2=10  <-- max so far
           h >= heights[1]=1, push 4 -> stack=[1,4]
i=5, h=3:  h > heights[4]=2, push 5 -> stack=[1,4,5]

Cleanup:
  pop 5: height=3, stack=[1,4], width=6-4-1=1, area=3*1=3
  pop 4: height=2, stack=[1],   width=6-1-1=4, area=2*4=8
  pop 1: height=1, stack=[],    width=6,        area=1*6=6

max_area = 10

The rectangle of area 10 is formed by bars at indices 2 and 3 (heights 5 and 6), using height 5 (the minimum). Width = 2. That is the answer.

Notice that bar 1 (height 1) stays in the stack the entire main loop — it is the global minimum, so it cannot be popped until cleanup, and then it spans the whole array (width 6, area 6).

Why O(n)?

Every bar index enters the stack exactly once (via stack.append) and leaves exactly once (via stack.pop). The total number of push+pop operations across the entire algorithm is exactly 2n. The while-loop inside the for-loop looks like it could add a factor, but each iteration of that while-loop is one pop — and there are at most n pops total. So the main loop is O(n), the cleanup loop is O(n), and the total is O(n). The stack uses O(n) space in the worst case (strictly increasing input like [1, 2, 3, 4, 5], where nothing ever pops until cleanup).

Edge cases that actually trip people up

Single bar (heights = [5]): i=0 pushes 5; main loop ends; cleanup pops it with stack=[], so width = n = 1, area = 5. Correct.

Strictly increasing ([1, 2, 3, 4]): nothing pops during the main loop — the monotonic property is never violated. All four bars end up in the stack. Cleanup processes them right to left: bar 3 gets width 1, bar 2 gets width 2, bar 1 gets width 3, bar 0 gets width 4. Maximum is 1*4 = 4. Correct — and this is the worst case for stack size.

Strictly decreasing ([4, 3, 2, 1]): every new bar triggers a pop. Bar 0 (height 4) is pushed, then popped immediately when bar 1 (height 3) arrives: width = 1, area = 4. Bar 1 is pushed, popped at bar 2: width = 2, area = 6. Bar 2 popped at bar 3: width = 3, area = 6. Bar 3 remains, cleanup: width = 4, area = 4. Maximum is 6 (bar at index 1, height 3, width 2).

All same height ([3, 3, 3]): heights are equal, so heights[i] < heights[stack[-1]] is false — no popping during main loop. All three push. Cleanup: bar 2 gets width 1, bar 1 gets width 2, bar 0 gets width 3. Maximum is 3*3 = 9.

Zero-height bar ([2, 0, 2]): bar 1 (height 0) triggers pops of everything taller. Bar 0 (height 2) is popped: stack=[], so width = 1, area = 2. Then bar 1 (height 0) is pushed. Then bar 2 (height 2) arrives — no pop. Cleanup pops bar 2: stack=[1], width = 3-1-1 = 1, area = 2. Then bar 1: stack=[], width = 3, area = 0. Maximum is 2. A zero-height bar is essentially a wall that resets everything. The code handles it naturally — area = 0 * anything = 0.

Overflow concern: heights[i] <= 10^4 and heights.length <= 10^5, so maximum area is 10^4 * 10^5 = 10^9. That fits in a 32-bit signed integer (max ~2.1 * 10^9), but only barely. In C# use int without concern; in Python integers are arbitrary precision.

Comparison table

The brute force's O(1) space advantage is real but irrelevant in practice. For n = 10^5 it times out. The stack's O(n) space is unavoidable — in the worst case (increasing input), every bar is in the stack simultaneously.

The mental model: a stack as a boundary oracle

The pattern here is "next smaller element" — for each element, find the first element to its right (or left) that is strictly smaller. This is a canonical monotonic stack application. The stack acts as a memory of "bars whose right boundary I have not yet found." When bar i arrives shorter than the top, it becomes the right boundary for everything it just popped.

The same oracle pattern appears in:

• Trapping Rain Water (42): instead of "how wide can this height extend," you ask "how much water sits above this bar." Monotonic stack again, but you are computing trapped volume rather than rectangular area. The pop-and-compute structure is nearly identical.
• Daily Temperatures (739): find the next warmer day for each day. Classic next-greater-element. The stack holds "days waiting for a warmer answer"; each new warmer day pops and resolves the waiting entries.
• Next Greater Element I and II (496, 503): the raw form of the pattern, without the area computation. 496 is a good warm-up if this problem feels too dense; 503 adds a circular array twist.
• Maximal Rectangle (85): extends this problem to a 2D matrix. Build a histogram for each row (each cell's height is how many consecutive 1s sit above it in the same column), then run this exact algorithm on each row's histogram. Same code, one nesting level deeper.

Where this sits in the stack series and what to write in an interview

This is the hardest stack problem in the series. Valid Parentheses taught the basic push-and-pop rhythm; Evaluate Reverse Polish Notation taught stack as a computation device; Min Stack added auxiliary tracking. Largest Rectangle in Histogram is the first problem where the stack's content is dynamic in a non-obvious way — you are maintaining a structural invariant (monotonic order) and using violations of that invariant as the trigger to compute answers.

What I would ship in a real interview: start by voicing the "each bar as minimum height" framing, sketch the brute force in two minutes, state the O(n²) complexity explicitly, then say "the redundancy is that we recompute boundaries we already know." That transition earns you the monotonic stack discussion. Implement the stack solution, walk through the trace above for [2, 1, 5, 6, 2, 3], and call out the width formula as the one thing that needs care (empty stack -> width = i or n).

I would reach for the monotonic stack immediately in production. The O(n²) brute force is never correct for n = 10^5. The stack adds O(n) memory but the time improvement from quadratic to linear is not negotiable at that scale. The code is about 15 lines in either language, and the invariant (indices in increasing height order) is easy to state and verify.