Largest Rectangle in Histogram — Monotonic Stack Masterclass

Problem Statement#

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Constraints:

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

Input:  heights = [2,1,5,6,2,3]
Output: 10  // rectangle of height 5 spanning indices 2..3 has area 5*2=10

Input:  heights = [2,4]
Output: 4

Why This Problem Matters#

LeetCode 84 Largest Rectangle in Histogram is the most important monotonic stack interview problem and shows up at Amazon, Google, Meta, Apple, and Microsoft. It is the canonical answer to "find for each element the next smaller element on each side," which is the building block of dozens of harder problems including Maximal Rectangle (LeetCode 85), Trapping Rain Water (LeetCode 42), and Sum of Subarray Minimums (LeetCode 907).

If you can write this in your sleep, you can solve a wide swath of FAANG hard interview questions. Recruiters know this and use this problem to confirm core monotonic stack mastery before moving on to derivatives.

The Core Insight#

For each bar i, the largest rectangle that uses bar i as the shortest bar is heights[i] times (R minus L minus 1), where L is the index of the nearest shorter bar to the left of i (or -1 if none) and R is the nearest shorter bar to the right (or n if none).

A naive computation of L and R is O(n squared). A monotonic increasing stack of indices gives both in amortized O(1) per bar:

• Maintain a stack of indices whose heights are strictly increasing from bottom to top.
• For each new bar i, while the top of stack has height greater than or equal to heights[i], pop it. The popped bar's "right boundary" is i, and its "left boundary" is the new top of stack after popping.
• Compute the area of the popped bar in O(1) and update the answer.
• Push i.

After processing the array, treat any remaining bars as if a virtual bar of height 0 came at index n.

Visual Dry Run#

heights equals [2, 1, 5, 6, 2, 3].

Maximum area equals 10. Matches expected output.

Notice how each index is pushed once and popped once, giving O(n) total.

Solution (Optimal)#

I append a sentinel 0 to flush the stack at the end, which simplifies the loop.

from typing import List
 
def largestRectangleArea(heights: List[int]) -> int:
    stack = []  # indices with strictly increasing heights
    best = 0
    heights = heights + [0]  # sentinel
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] >= h:
            top = stack.pop()
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, heights[top] * width)
        stack.append(i)
    return best

function largestRectangleArea(heights) {
  const stack = [];
  let best = 0;
  const arr = [...heights, 0]; // sentinel
  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
      const top = stack.pop();
      const left = stack.length ? stack[stack.length - 1] : -1;
      const width = i - left - 1;
      best = Math.max(best, arr[top] * width);
    }
    stack.push(i);
  }
  return best;
}

Complexity. Time O(n) — each index is pushed and popped at most once. Space O(n) for the stack in the worst case (strictly increasing input).

Common Mistakes#

• Computing left and right boundaries in two separate passes. It works (still O(n)), but doing both in one pass is cleaner.
• Storing heights instead of indices on the stack. You need indices to compute width.
• Off-by-one in width calculation. The correct formula is i minus left minus 1, where left is the new top after popping (or -1 if empty).
• Forgetting the sentinel at the end and leaving stack contents unflushed. Without the sentinel, you must add a separate flush loop.
• Using less-than (strict) instead of less-than-or-equal when popping. Equality must also pop because equal-height bars to the left are dominated by the new bar.

Interview Tips#

• State the brute force O(n squared) and reject it. Then introduce the monotonic stack as "for each bar, I want the nearest smaller bar on each side."
• Walk through the dry run on the whiteboard with at least three pops to make the boundary logic concrete.
• Articulate the invariant: stack holds indices with strictly increasing heights from bottom to top.
• Mention the sentinel trick — it eliminates a special-case flush loop and is a hallmark of clean monotonic stack code.
• Discuss the connection to other problems (Maximal Rectangle, Trapping Rain Water) so the interviewer sees you grasp the pattern.

Follow-up Questions#

1. What if heights is updated dynamically? Use a segment tree of (min, count) for range minimum queries with O(log n) updates.
2. What is the largest k by k square with all heights at least h? Reduce to range minimum query plus binary search.
3. What if widths are not all 1? Multiply heights[top] times sum-of-widths between L and R; cumulative width array helps.
4. How would you parallelize this? Divide into chunks, compute per-chunk monotonic stacks, merge boundary regions carefully.
5. What is the largest rectangle of equal heights only? Different problem — track runs separately.

Key Takeaways#

• Monotonic increasing stack of indices is the canonical solution for "nearest smaller on each side."
• For each popped bar, the right boundary is the current index and the left boundary is the new top after popping.
• A sentinel 0 at the end eliminates the post-loop flush.
• Time O(n), space O(n) — strictly better than O(n log n) divide-and-conquer.
• This is the foundation for Maximal Rectangle, Trapping Rain Water, Sum of Subarray Minimums, and many more.
• Mastering this problem unlocks a large slice of FAANG hard interview questions.