W
← Blog/dsaarraysstrings

Largest Rectangle in Histogram [Hard] — Monotonic Stack Deep Dive [Amazon, Google]

Sanjeev SharmaSanjeev Sharma
17 min read

Advertisement

Problem Statement

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

Examples:

Input:  heights = [2, 1, 5, 6, 2, 3]
Output: 10
Reason: Rectangle of height 5 spanning bars at indices 2 and 3 (heights 5 and 6).
        Width = 2, height = 5, area = 10.

Input:  heights = [2, 4]
Output: 4
Reason: Single bar of height 4, width 1.

ASCII visualization of [2, 1, 5, 6, 2, 3]:

        _
      _| |
     | | |
     | | |_ _
  _  | | | | |
_| |_| | | | |_
 2  1  5  6  2  3

The 10-unit rectangle (height 5 × width 2) is shaded over bars 2 and 3:
      [=====]
      [=====]
      [=====]
      [=====]
  _   [=====]_
_| |_ [=====] |_
 2  1   5   6  2  3

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

Why This Problem Matters

LeetCode 84 is one of the most asked Hard problems in FAANG technical interviews — Amazon lists it explicitly in their interview preparation materials, and Google uses it to test whether candidates can think in terms of monotonic data structures rather than brute-force enumeration.

But why does this problem matter beyond interviews? It is the canonical teaching problem for the monotonic stack pattern — a technique that appears in dozens of competitive programming and real-world algorithm problems:

  • Trapping Rain Water (LC 42): Conceptually symmetric — instead of finding how high a rectangle extends upward, you find how much water fills downward between taller bars.
  • Maximal Rectangle in Binary Matrix (LC 85): A direct extension — treat each row of the matrix as a histogram, then run LC 84's algorithm on each row. This transforms a 2D hard problem into a series of 1D hard problems, each solved in O(n).
  • Sum of Subarray Minimums (LC 907): Uses the same "previous smaller / next smaller" framework.
  • Online Stock Span (LC 901): A streaming variant of the monotonic stack.

The core insight this problem teaches — maintain a stack that automatically reveals left/right boundaries when you pop — is something interviewers specifically watch for. Candidates who see it think in O(n); candidates who miss it write O(n²) nested loops.

Interview frequency: This problem appears in roughly 1 in 8 on-site rounds at Amazon and Google for SDE-2 and above roles. A common pattern is asking LC 42 (Trapping Rain Water) as a warm-up, then following with LC 84 to see if the candidate recognizes the structural similarity.

The Key Observation

Before touching a stack, think carefully about what determines the largest rectangle involving any specific bar.

For a bar at index i with height h, the largest rectangle using that bar as the bottleneck height (meaning h is the minimum height across the rectangle's span) extends:

  • Left as far as possible — until you hit a bar strictly shorter than h, or the left edge of the array.
  • Right as far as possible — until you hit a bar strictly shorter than h, or the right edge of the array.

Formally, define:

  • left[i] = index of the nearest bar to the left of i that is strictly shorter than heights[i]
  • right[i] = index of the nearest bar to the right of i that is strictly shorter than heights[i]

Then the area of the largest rectangle with bar i as its height is:

area[i] = heights[i] × (right[i] - left[i] - 1)

The answer is max(area[0], area[1], ..., area[n-1]).

This is the "previous smaller element / next smaller element" formulation. Computing both arrays naively takes O(n) space and O(n²) time per pair, but a monotonic stack can compute both simultaneously in a single pass, in O(n) total.

Brute Force — O(n²)

The straightforward approach: for every possible left boundary l and right boundary r, compute the area of the rectangle spanning l to r. The height of such a rectangle is the minimum height in heights[l..r].

But we can simplify: for a fixed left boundary l, extend rightward one bar at a time, tracking the running minimum height, and updating the maximum area.

Python:

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        max_area = 0

        for left in range(n):
            min_height = heights[left]           # minimum height in current span
            for right in range(left, n):
                min_height = min(min_height, heights[right])   # extend span, update min
                width = right - left + 1
                max_area = max(max_area, min_height * width)   # area = min_height × width

        return max_area

JavaScript:

function largestRectangleArea(heights) {
    let maxArea = 0;
    const n = heights.length;

    for (let left = 0; left < n; left++) {
        let minHeight = heights[left];           // running minimum for this span
        for (let right = left; right < n; right++) {
            minHeight = Math.min(minHeight, heights[right]);   // extend, update min
            const width = right - left + 1;
            maxArea = Math.max(maxArea, minHeight * width);    // track global max
        }
    }

    return maxArea;
}

Why this is too slow: For n = 100,000, we execute roughly 5 billion operations. Even at 10^9 operations per second, that is 5,000 seconds. This will TLE on LeetCode. We need O(n).

The Monotonic Stack Approach

The Core Idea

We want to process each bar and, at the right moment, calculate the rectangle for which that bar is the height bottleneck. The "right moment" is precisely when we encounter the first bar shorter than the current bar scanning left to right.

Why? Because that shorter bar is the right boundary — the rectangle at the current height cannot extend past it. At the same instant, the item just below in the stack is the left boundary — nothing between it and the current index is shorter than the current bar (the stack's monotonically increasing property guarantees this).

We maintain a stack of indices (not heights) in strictly increasing height order from bottom to top.

Algorithm

for each index i in [0, n):
    while stack is not empty AND heights[i] < heights[stack.top()]:
        popped_idx   = stack.pop()
        height       = heights[popped_idx]
        right_bound  = i                                      # current bar is the right boundary
        left_bound   = stack.top() if stack else -1           # new top is the left boundary
        width        = right_bound - left_bound - 1
        area         = height × width
        update max_area
    stack.push(i)

# After the loop, anything remaining in the stack has no right boundary (extends to array end)
# Handle them the same way with right_bound = n

Why left_bound = stack.top() (not stack.top() + 1)

This is the most commonly misunderstood part. After popping popped_idx, the new stack top represents the nearest bar to the left that is strictly shorter than heights[popped_idx]. Since that bar is shorter, it is excluded from our rectangle — our rectangle starts one position to the right of left_bound. But we do not need to add 1 explicitly, because the width formula right_bound - left_bound - 1 already handles this:

width = right_bound - left_bound - 1
      = i - stack.top() - 1

This counts the number of indices strictly between left_bound and right_bound — exactly the span of our rectangle.

Why store indices, not heights?

Because when we pop a bar and need to compute width, we need to know the position of the left boundary. If we stored heights, we would have no way to look up the index of the item below in the stack. Always store indices; look up heights as heights[stack.top()].

The Sentinel Values Trick

Without sentinels, the algorithm has an awkward edge case: bars remaining in the stack after the main loop never triggered a pop (because no shorter bar appeared to their right). You need a separate cleanup loop:

# Without sentinel — two-phase approach (fragile)
while stack:
    popped_idx = stack.pop()
    height = heights[popped_idx]
    left_bound = stack[-1] if stack else -1
    width = n - left_bound - 1
    max_area = max(max_area, height * width)

This works, but the two-phase structure is a common source of off-by-one bugs under interview pressure.

The elegant fix: append a sentinel bar of height 0 at the end of the array. Since 0 is shorter than every real bar, it forces every remaining bar out of the stack during the main loop. No cleanup loop needed. The sentinel's pop is always area = 0 * width = 0, so it never incorrectly updates max_area.

heights.append(0)   # sentinel forces all bars to pop
# ... run main loop ...
heights.pop()       # restore array (polite practice)

Some implementations also prepend a 0 at the start (giving left_bound = -1 semantics automatically), but only the trailing sentinel is truly necessary. The trailing sentinel alone is sufficient and is the standard interview answer.

Visual Dry Run — [2, 1, 5, 6, 2, 3]

With sentinel appended: [2, 1, 5, 6, 2, 3, 0] (index 6 is the sentinel).

We track: stack (list of indices), heights[stack] for readability, and max_area.

i = 0, h = 2: Stack is empty. Push 0.

stack = [0]   heights = [2]   max_area = 0

i = 1, h = 1: heights[1] = 1 < heights[stack.top()] = heights[0] = 2 → pop index 0.

  • height = 2, right_bound = 1, left_bound = -1 (stack empty after pop)
  • width = 1 - (-1) - 1 = 1, area = 2 × 1 = 2

Stack is now empty; h = 1 is not less than anything. Push 1.

stack = [1]   heights = [1]   max_area = 2

i = 2, h = 5: 5 > heights[1] = 1 — no pop. Push 2.

stack = [1, 2]   heights = [1, 5]   max_area = 2

i = 3, h = 6: 6 > heights[2] = 5 — no pop. Push 3.

stack = [1, 2, 3]   heights = [1, 5, 6]   max_area = 2

i = 4, h = 2: 2 < heights[stack.top()] = heights[3] = 6 → pop index 3.

  • height = 6, right_bound = 4, left_bound = stack.top() = 2
  • width = 4 - 2 - 1 = 1, area = 6 × 1 = 6
  • max_area = max(2, 6) = 6

2 < heights[stack.top()] = heights[2] = 5 → pop index 2.

  • height = 5, right_bound = 4, left_bound = stack.top() = 1
  • width = 4 - 1 - 1 = 2, area = 5 × 2 = 10
  • max_area = max(6, 10) = 10

2 > heights[stack.top()] = heights[1] = 1 — stop popping. Push 4.

stack = [1, 4]   heights = [1, 2]   max_area = 10

i = 5, h = 3: 3 > heights[4] = 2 — no pop. Push 5.

stack = [1, 4, 5]   heights = [1, 2, 3]   max_area = 10

i = 6, h = 0 (sentinel): 0 < heights[5] = 3 → pop index 5.

  • height = 3, right_bound = 6, left_bound = 4
  • width = 6 - 4 - 1 = 1, area = 3 × 1 = 3

0 < heights[4] = 2 → pop index 4.

  • height = 2, right_bound = 6, left_bound = 1
  • width = 6 - 1 - 1 = 4, area = 2 × 4 = 8

0 < heights[1] = 1 → pop index 1.

  • height = 1, right_bound = 6, left_bound = -1 (stack empty after pop)
  • width = 6 - (-1) - 1 = 6, area = 1 × 6 = 6

Stack empty. Push 6 (sentinel). Loop ends.

stack = [6]   max_area = 10

Final answer: 10. This corresponds to the 5 × 2 rectangle over indices 2 and 3.

Common Mistakes

Mistake 1: Storing heights instead of indices in the stack

# WRONG — you lose position information needed for width calculation
stack.append(heights[i])

# CORRECT — always store indices, look up heights as heights[stack[-1]]
stack.append(i)

Mistake 2: Using the wrong left boundary formula

# WRONG — this is the index of the bar we just popped, not the boundary
width = i - popped_idx - 1

# CORRECT — after popping, the new stack top is the left boundary
left_bound = stack[-1] if stack else -1
width = i - left_bound - 1

The left boundary is the new stack top after the pop, not the popped index minus one. These happen to be the same when bars are adjacent, but diverge when there are gaps (e.g., multiple pops in a single iteration).

Mistake 3: Forgetting the empty stack case for left boundary

When the stack is empty after popping, it means the popped bar is taller than all bars to its left. The rectangle extends all the way to the left edge, so left_bound = -1, giving width = right_bound - (-1) - 1 = right_bound.

left_bound = stack[-1] if stack else -1   # CORRECT — handle empty stack

Mistake 4: Not using a sentinel (or adding cleanup loop incorrectly)

Without the sentinel, bars with no shorter bar to their right stay in the stack forever. Either add the sentinel or write a correct cleanup loop after the main loop. The sentinel approach is strongly preferred — it is cleaner and less error-prone.

Solutions

Brute Force — O(n²) time, O(1) space

(Already shown above — reference for completeness.)

Monotonic Stack with Sentinel — O(n) time, O(n) space

Python:

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # Append sentinel: forces all bars to be processed without a cleanup loop
        heights.append(0)
        stack = []         # stores indices; heights are monotonically increasing bottom-to-top
        max_area = 0

        for i, h in enumerate(heights):
            # While current bar is shorter than stack top, the top bar found its right boundary
            while stack and h < heights[stack[-1]]:
                popped_idx = stack.pop()
                height = heights[popped_idx]

                # Left boundary: new stack top (the nearest shorter bar to the left)
                # If stack is empty, the rectangle extends to the left edge (left_bound = -1)
                left_bound = stack[-1] if stack else -1

                # Width spans from left_bound+1 to i-1 (exclusive of both boundaries)
                width = i - left_bound - 1
                max_area = max(max_area, height * width)

            stack.append(i)

        # Restore the array (good practice — avoids mutating caller's data)
        heights.pop()
        return max_area

JavaScript:

/**
 * @param {number[]} heights
 * @return {number}
 */
function largestRectangleArea(heights) {
    // Sentinel forces all remaining bars to be popped and computed
    heights.push(0);
    const stack = [];     // indices; heights increase from bottom to top
    let maxArea = 0;
    const n = heights.length;

    for (let i = 0; i < n; i++) {
        // Pop bars that are taller than the current bar (current is their right boundary)
        while (stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]) {
            const poppedIdx = stack.pop();
            const height = heights[poppedIdx];

            // Left boundary: new stack top, or -1 if stack is now empty
            const leftBound = stack.length > 0 ? stack[stack.length - 1] : -1;

            // Width = number of positions strictly between leftBound and i
            const width = i - leftBound - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        stack.push(i);
    }

    // Restore array
    heights.pop();
    return maxArea;
}

Complexity Analysis

ApproachTimeSpaceNotes
Brute ForceO(n²)O(1)Two nested loops; TLEs for n > 50,000
Monotonic StackO(n)O(n)Each bar pushed and popped exactly once

Why is the monotonic stack O(n)?

The key is the amortized analysis. Although the inner while loop appears nested inside the outer for loop, each bar is pushed into the stack exactly once and popped from the stack exactly once over the entire execution. So across all iterations combined, there are at most n push operations and at most n pop operations — giving 2n total stack operations, which is O(n).

The sentinel adds one extra push and at most n pops (forcing the remaining bars), which is still O(n) total.

Space: The stack holds at most n indices at any given time (all bars pushed before any pop), so O(n) space.

Follow-up Questions

1. Maximal Rectangle (LC 85) — Hard

"Given a 2D binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area."

This is a direct extension of LC 84. The key insight: for each row, build a heights array where heights[j] equals the number of consecutive 1s directly above (row, j) including (row, j) itself (reset to 0 when you hit a 0). Then each row's heights array is exactly a histogram — apply LC 84's monotonic stack algorithm to it.

def maximalRectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    n = len(matrix[0])
    heights = [0] * n
    max_area = 0

    for row in matrix:
        # Update histogram heights for this row
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0

        # Run LC 84 on this row's histogram
        max_area = max(max_area, largestRectangleArea(heights[:]))  # LC 84 solution

    return max_area

Complexity: O(m × n) time, O(n) space — where m is the number of rows.

2. Trapping Rain Water (LC 42) — Hard

"Given an elevation map, compute how much water it can trap after raining."

Structurally related: instead of finding how tall a rectangle extends upward with a bar as the floor, you find how much water fills downward between two taller surrounding bars. The same "previous larger / next larger" boundary reasoning applies, and a monotonic stack (this time decreasing, not increasing) solves it in O(n).

Understanding LC 84 deeply makes LC 42 significantly easier, since you already have the mental model for how stack tops reveal boundaries.

3. Maximum Width Ramp (LC 962) — Medium

Uses a monotonic stack of "candidate left boundaries" in decreasing height order, then sweeps right to find the widest valid span. Same boundary-revelation pattern.

4. Largest Rectangle in Binary Matrix (variant of LC 85)

If the matrix contains arbitrary integers rather than 0/1, you can still apply a histogram approach: define "height" at each cell as the length of the longest consecutive non-zero run ending at that cell in the column direction.

This Pattern Solves

Other problems that use the monotonic stack's boundary-revelation property:

ProblemHow the Pattern Applies
Trapping Rain Water (LC 42)Decreasing stack; popping reveals water level
Daily Temperatures (LC 739)Next greater element — pop when a warmer day appears
Sum of Subarray Minimums (LC 907)Previous/next smaller for each element's contribution
Online Stock Span (LC 901)Streaming version — pop while previous prices are lower
Buildings With an Ocean View (LC 1762)Monotonic decreasing stack of visible buildings
Largest Rectangle in Binary Matrix (LC 85)LC 84 applied row-by-row
Remove K Digits (LC 402)Maintain monotonic stack of digits, pop greedily

Key Takeaway

The largest rectangle in histogram problem is hard not because the code is long, but because the invariant is non-obvious: a monotonically increasing stack automatically and simultaneously tracks both the left and right boundaries for every bar, revealing them the instant you need them (when a shorter bar triggers a pop). The moment you internalize "pop = right boundary found, new top = left boundary," you can solve this problem in five minutes and extend the same thinking to an entire family of hard problems. Always store indices in the stack, never heights, and use the sentinel trick to eliminate the cleanup loop — your interviewer will notice both.

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro

twitterlinkedingithubmail

← Previous

Minimum Window Substring [Hard] — The Canonical Sliding Window Problem

Next →

First Missing Positive [Hard] — The Definitive Index-Marking Guide [Amazon, Google, Microsoft]