Problem statement

Given an array heights of bar heights (each bar has width 1), return the area of the largest rectangle that fits inside the histogram.

Example 1

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The rectangle spans bars 5 and 6 with height 5.

Example 2

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

Constraints

• 1 <= heights.length <= 35
• 0 <= heights[i] <= 100

Hints for Largest Rectangle in Histogram

1. Hint 1

   For each bar, the best rectangle using its full height spans to the nearest shorter bar on each side.

2. Hint 2

   A monotonic increasing stack finds both boundaries in one pass — append a sentinel 0 to flush.

How to solve Largest Rectangle in Histogram

Every maximal rectangle is limited by its shortest bar, so it is enough to ask, for each bar: if this bar's full height is the ceiling, how wide can the rectangle get? It stretches left and right until it meets a strictly shorter bar. Finding those two boundaries naively is O(n²); a single monotonic stack finds both in one pass.

Approach

1. Append a sentinel bar of height 0 to the array. It is shorter than everything, so it forces the stack to drain at the end.
2. Keep a stack of indices whose heights increase from the bottom to the top.
3. For each index i: while the bar at the top of the stack is taller than h[i], pop it. That popped bar's rectangle ends here.
4. For the popped index, its height is h[popped], its right boundary is i, and its left boundary is the index now on top of the stack (or -1 if the stack is empty). The width is i - left - 1.
5. Update the best area with height × width, then push i.

Why it works

When index j is popped at i, i is the first bar to the right of j that is shorter than h[j] — anything taller was pushed above j and popped before it. The entry directly below j is, by the increasing invariant, the nearest bar to the left shorter than h[j]. So the span between those two boundaries is exactly the widest rectangle of height h[j], and since every bar is popped exactly once, every candidate is considered.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The width is i - left - 1, using the element below the popped one — not i - popped. Getting this wrong is the single most common bug here.
• Without the sentinel 0, bars still on the stack at the end are never measured, and an increasing histogram returns a far too small answer.
• The left boundary is -1 when the stack empties, meaning the rectangle reaches the start of the array.
• Heights may be 0, which is fine — such a bar contributes area 0 and acts as a natural divider.

Reference solution

Python

from typing import List

def largestRectangleArea(heights: List[int]) -> int:
    st = []
    best = 0
    hs = heights + [0]
    for i, h in enumerate(hs):
        while st and hs[st[-1]] > h:
            height = hs[st.pop()]
            left = st[-1] if st else -1
            best = max(best, height * (i - left - 1))
        st.append(i)
    return best

Java

public static int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] h = new int[n + 1];
    for (int i = 0; i < n; i++) h[i] = heights[i];
    h[n] = 0;
    Deque<Integer> st = new ArrayDeque<>();
    int best = 0;
    for (int i = 0; i <= n; i++) {
        while (!st.isEmpty() && h[st.peek()] > h[i]) {
            int height = h[st.pop()];
            int left = st.isEmpty() ? -1 : st.peek();
            best = Math.max(best, height * (i - left - 1));
        }
        st.push(i);
    }
    return best;
}

C++

int largestRectangleArea(vector<int>& heights) {
    vector<int> h = heights;
    h.push_back(0);
    vector<int> st;
    int best = 0;
    for (int i = 0; i < (int) h.size(); i++) {
        while (!st.empty() && h[st.back()] > h[i]) {
            int height = h[st.back()];
            st.pop_back();
            int left = st.empty() ? -1 : st.back();
            best = max(best, height * (i - left - 1));
        }
        st.push_back(i);
    }
    return best;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard