84. Largest Rectangle in Histogram (Hard)

Problem

Given heights representing a histogram (unit-width bars), return the area of the largest rectangle that fits entirely inside the histogram.

Example

heights = [2,1,5,6,2,3] → 10 (bars of heights 5 and 6 form a 2×5 rectangle)
heights = [2,4] → 4

LeetCode 84 · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, expand around each bar

For each bar i, find how far left and right you can extend while heights stay ≥ heights[i]. The rectangle with bar i as the shortest is heights[i] * width.

def largest_rectangle_area(heights: list[int]) -> int:
    n = len(heights)                               # L1: O(1)
    best = 0                                       # L2: O(1)
    for i in range(n):                             # L3: outer loop, n iterations
        h = heights[i]                             # L4: O(1)
        # Expand left
        l = i
        while l - 1 >= 0 and heights[l - 1] >= h: # L5: expand left, up to i steps
            l -= 1                                 # L6: O(1)
        # Expand right
        r = i
        while r + 1 < n and heights[r + 1] >= h:  # L7: expand right, up to n-i steps
            r += 1                                 # L8: O(1)
        best = max(best, h * (r - l + 1))          # L9: O(1) area
    return best

function largestRectangleArea(heights: number[]): number {
    const n = heights.length;                        // L1: O(1)
    let best = 0;                                    // L2: O(1)
    for (let i = 0; i < n; i++) {                   // L3: outer loop, n iterations
        const h = heights[i];                        // L4: O(1)
        let l = i;
        while (l - 1 >= 0 && heights[l - 1] >= h) l--;  // L5-L6: expand left
        let r = i;
        while (r + 1 < n && heights[r + 1] >= h) r++;   // L7-L8: expand right
        best = Math.max(best, h * (r - l + 1));      // L9: O(1) area
    }
    return best;
}

func largestRectangleArea(heights []int) int {
    n := len(heights)                               // L1: O(1)
    best := 0                                       // L2: O(1)
    for i := 0; i < n; i++ {                       // L3: outer loop, n iterations
        h := heights[i]                             // L4: O(1)
        l := i
        for l-1 >= 0 && heights[l-1] >= h {        // L5-L6: expand left
            l--
        }
        r := i
        for r+1 < n && heights[r+1] >= h {         // L7-L8: expand right
            r++
        }
        area := h * (r - l + 1)                    // L9: O(1) area
        if area > best {
            best = area
        }
    }
    return best
}

final class Solution {
    func largestRectangleArea(_ heights: [Int]) -> Int {
        var best = 0
        for left in heights.indices {
            var minimum = heights[left]
            for right in left..<heights.count {
                minimum = min(minimum, heights[right])
                best = max(best, minimum * (right - left + 1))
            }
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(heights).

Line	Per-call cost	Times executed	Contribution
L3 (outer loop)	$O(1)$	n	$O(n)$
L5-L8 (expand left + right)	$O(1)$ per step	up to n per outer	$O(n²)$ ← dominates
L9 (area)	$O(1)$	n	$O(n)$

In the worst case (a monotonic histogram), each bar expands across the entire remaining array.

Complexity

Time: $O(n²)$ , driven by L5-L8 (worst-case full expansion per bar).
Space: $O(1)$ .

Approach 2: Precompute nearest-smaller arrays

For each index, precompute:

left[i], index of nearest bar strictly smaller on the left (or -1).
right[i], index of nearest bar strictly smaller on the right (or n).

Then area with bar i as the minimum is heights[i] * (right[i] - left[i] - 1).

def largest_rectangle_area(heights: list[int]) -> int:
    n = len(heights)                               # L1: O(1)
    left = [-1] * n                                # L2: O(n)
    right = [n] * n                                # L3: O(n)

    stack = []
    for i in range(n):                             # L4: forward pass for left[]
        while stack and heights[stack[-1]] >= heights[i]:  # L5: pop larger
            stack.pop()                            # L6: O(1) amortized
        left[i] = stack[-1] if stack else -1       # L7: O(1)
        stack.append(i)                            # L8: O(1)

    stack = []
    for i in range(n - 1, -1, -1):                # L9: backward pass for right[]
        while stack and heights[stack[-1]] >= heights[i]:  # L10: pop larger
            stack.pop()                            # L11: O(1) amortized
        right[i] = stack[-1] if stack else n       # L12: O(1)
        stack.append(i)                            # L13: O(1)

    return max((heights[i] * (right[i] - left[i] - 1) for i in range(n)), default=0)  # L14: O(n)

function largestRectangleArea(heights: number[]): number {
    const n = heights.length;
    const left = new Array(n).fill(-1);            // L2: O(n)
    const right = new Array(n).fill(n);            // L3: O(n)

    let stack: number[] = [];
    for (let i = 0; i < n; i++) {                 // L4: forward pass for left[]
        while (stack.length && heights[stack[stack.length - 1]] >= heights[i])
            stack.pop();                           // L5-L6: O(1) amortized
        left[i] = stack.length ? stack[stack.length - 1] : -1;  // L7: O(1)
        stack.push(i);                             // L8: O(1)
    }

    stack = [];
    for (let i = n - 1; i >= 0; i--) {            // L9: backward pass for right[]
        while (stack.length && heights[stack[stack.length - 1]] >= heights[i])
            stack.pop();                           // L10-L11: O(1) amortized
        right[i] = stack.length ? stack[stack.length - 1] : n;  // L12: O(1)
        stack.push(i);                             // L13: O(1)
    }

    let best = 0;
    for (let i = 0; i < n; i++)
        best = Math.max(best, heights[i] * (right[i] - left[i] - 1));  // L14: O(n)
    return best;
}

func largestRectangleArea(heights []int) int {
    n := len(heights)
    left := make([]int, n)
    right := make([]int, n)
    stack := []int{}

    for i := 0; i < n; i++ {                      // L4: forward pass for left[]
        for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
            stack = stack[:len(stack)-1]           // L5-L6: O(1) amortized
        }
        if len(stack) > 0 {
            left[i] = stack[len(stack)-1]          // L7: O(1)
        } else {
            left[i] = -1
        }
        stack = append(stack, i)                   // L8: O(1)
    }

    stack = []int{}
    for i := n - 1; i >= 0; i-- {                 // L9: backward pass for right[]
        for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
            stack = stack[:len(stack)-1]           // L10-L11: O(1) amortized
        }
        if len(stack) > 0 {
            right[i] = stack[len(stack)-1]         // L12: O(1)
        } else {
            right[i] = n
        }
        stack = append(stack, i)                   // L13: O(1)
    }

    best := 0
    for i := 0; i < n; i++ {
        area := heights[i] * (right[i] - left[i] - 1)  // L14: O(n)
        if area > best {
            best = area
        }
    }
    return best
}

final class Solution {
    func largestRectangleArea(_ heights: [Int]) -> Int {
        guard !heights.isEmpty else { return 0 }
        var left = Array(repeating: -1, count: heights.count)
        var right = Array(repeating: heights.count, count: heights.count)
        var stack: [Int] = []
        for index in heights.indices {
            while let last = stack.last, heights[last] >= heights[index] { stack.removeLast() }
            left[index] = stack.last ?? -1
            stack.append(index)
        }
        stack.removeAll()
        for index in heights.indices.reversed() {
            while let last = stack.last, heights[last] >= heights[index] { stack.removeLast() }
            right[index] = stack.last ?? heights.count
            stack.append(index)
        }
        return heights.indices.map { heights[$0] * (right[$0] - left[$0] - 1) }.max() ?? 0
    }
}

Where the time goes, line by line

Variables: n = len(heights).

Line	Per-call cost	Times executed	Contribution
L2, L3 (init arrays)	$O(n)$	1 each	$O(n)$
L4-L8 (left pass, stack)	$O(1)$ amortized	n	$O(n)$
L9-L13 (right pass, stack)	$O(1)$ amortized	n	$O(n)$
L14 (compute max)	$O(1)$ per element	n	$O(n)$

Each index is pushed and popped at most once per pass; the stack operations are $O(n)$ total per pass.

Complexity

Time: $O(n)$ , driven by L4-L8 and L9-L13 (two linear monotonic-stack passes).
Space: $O(n)$ for the left/right arrays and stack.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Single monotonic stack pass (optimal)

Maintain a stack of indices whose heights are monotonically increasing. When a shorter bar comes in, pop the top and compute the rectangle where the popped bar is the shortest, bounded on the right by the current index and on the left by the new stack top. A sentinel (bar of height 0) at the end flushes the stack.

def largest_rectangle_area(heights: list[int]) -> int:
    stack = []                             # L1: O(1), indices with increasing heights
    best = 0                               # L2: O(1)
    heights = heights + [0]                # L3: O(n) sentinel appended
    for i, h in enumerate(heights):        # L4: n+1 iterations
        while stack and heights[stack[-1]] > h:  # L5: pop taller bars
            top = stack.pop()              # L6: O(1) amortized pop
            height = heights[top]          # L7: O(1)
            width = i if not stack else i - stack[-1] - 1  # L8: O(1) width
            best = max(best, height * width)  # L9: O(1) update
        stack.append(i)                    # L10: O(1) push
    return best

function largestRectangleArea(heights: number[]): number {
    const h = [...heights, 0];               // L3: sentinel appended
    const stack: number[] = [];
    let best = 0;
    for (let i = 0; i < h.length; i++) {    // L4: n+1 iterations
        while (stack.length && h[stack[stack.length - 1]] > h[i]) {  // L5: pop taller bars
            const top = stack.pop()!;        // L6: O(1) amortized pop
            const height = h[top];           // L7: O(1)
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;  // L8: O(1) width
            best = Math.max(best, height * width);  // L9: O(1) update
        }
        stack.push(i);                       // L10: O(1) push
    }
    return best;
}

func largestRectangleArea(heights []int) int {
    h := append(heights, 0)                // L3: sentinel appended
    stack := []int{}
    best := 0
    for i := 0; i < len(h); i++ {         // L4: n+1 iterations
        for len(stack) > 0 && h[stack[len(stack)-1]] > h[i] {  // L5: pop taller bars
            top := stack[len(stack)-1]     // L6: O(1) amortized pop
            stack = stack[:len(stack)-1]
            height := h[top]               // L7: O(1)
            width := i                     // L8: O(1) width
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            area := height * width         // L9: O(1) update
            if area > best {
                best = area
            }
        }
        stack = append(stack, i)           // L10: O(1) push
    }
    return best
}

final class Solution {
    func largestRectangleArea(_ heights: [Int]) -> Int {
        var best = 0
        var stack: [(start: Int, height: Int)] = []
        for index in 0...heights.count {
            let height = index == heights.count ? 0 : heights[index]
            var start = index
            while let last = stack.last, last.height > height {
                let bar = stack.removeLast()
                best = max(best, bar.height * (index - bar.start))
                start = bar.start
            }
            stack.append((start, height))
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(heights) (before sentinel).

Line	Per-call cost	Times executed	Contribution
L3 (sentinel)	$O(n)$	1	$O(n)$
L4 (outer loop)	$O(1)$	n+1	$O(n)$
L5-L10 (stack ops + area)	$O(1)$ amortized	n total pushes/pops	$O(n)$ ← dominates

Each bar is pushed exactly once and popped at most once; the total push+pop count is 2n, giving $O(n)$ amortized.

Complexity

Time: $O(n)$ , driven by L5-L10 (each bar pushed and popped at most once).
Space: $O(n)$ stack.

Intuition

The stack stores “bars that are still candidates for being the left boundary of some rectangle.” When a new bar breaks the increasing property, the popped bar’s maximal rectangle is determined, extend it leftward until the new top of the stack (the first bar shorter than the popped one on its left) and rightward to the current index.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Expand-around	$O(n²)$	$O(1)$
Nearest-smaller arrays	$O(n)$	$O(n)$
Single monotonic stack	$O(n)$	$O(n)$

This problem is a rite of passage for monotonic stacks. It also unlocks 85. Maximal Rectangle (apply this per row of a binary matrix).

Test cases

# Quick smoke tests, paste into a REPL or save as test_largest_rectangle.py and run.
# Uses the canonical implementation (Approach 3: single monotonic stack).

def largest_rectangle_area(heights: list[int]) -> int:
    stack = []
    best = 0
    heights = heights + [0]
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            height = heights[top]
            width = i if not stack else i - stack[-1] - 1
            best = max(best, height * width)
        stack.append(i)
    return best

def _run_tests():
    assert largest_rectangle_area([2, 1, 5, 6, 2, 3]) == 10
    assert largest_rectangle_area([2, 4]) == 4
    assert largest_rectangle_area([1]) == 1
    assert largest_rectangle_area([6, 5, 4, 3, 2, 1]) == 12
    assert largest_rectangle_area([1, 2, 3, 4, 5, 6]) == 12
    assert largest_rectangle_area([2, 0, 2]) == 2
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

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

console.assert(largestRectangleArea([2, 1, 5, 6, 2, 3]) === 10);
console.assert(largestRectangleArea([2, 4]) === 4);
console.assert(largestRectangleArea([1]) === 1);
console.assert(largestRectangleArea([6, 5, 4, 3, 2, 1]) === 12);
console.assert(largestRectangleArea([1, 2, 3, 4, 5, 6]) === 12);
console.assert(largestRectangleArea([2, 0, 2]) === 2);
console.log('all tests pass');

func largestRectangleArea(heights []int) int {
    h := append(heights, 0)
    stack := []int{}
    best := 0
    for i := 0; i < len(h); i++ {
        for len(stack) > 0 && h[stack[len(stack)-1]] > h[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            height := h[top]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            area := height * width
            if area > best {
                best = area
            }
        }
        stack = append(stack, i)
    }
    return best
}

func main() {
    assert := func(b bool) {
        if !b { panic("assertion failed") }
    }
    assert(largestRectangleArea([]int{2, 1, 5, 6, 2, 3}) == 10)
    assert(largestRectangleArea([]int{2, 4}) == 4)
    assert(largestRectangleArea([]int{1}) == 1)
    assert(largestRectangleArea([]int{6, 5, 4, 3, 2, 1}) == 12)
    assert(largestRectangleArea([]int{1, 2, 3, 4, 5, 6}) == 12)
    assert(largestRectangleArea([]int{2, 0, 2}) == 2)
    fmt.Println("all tests pass")
}

Arrays, histogram
Stacks, monotonic increasing stack for left/right nearest-smaller

Monotonic Stack, the ordered stack pattern for nearest greater, nearest smaller, and spans.
Array Scans, the linear pass habit of carrying just enough state while reading each item once.

84. Largest Rectangle in Histogram (Hard)

Problem

Try it yourself

Approach 1: Brute force, expand around each bar

Approach 2: Precompute nearest-smaller arrays

Approach 3: Single monotonic stack pass (optimal)

Intuition

Summary

Test cases

Related data structures

Related concepts