Largest Rectangle in Histogram

You are given an array of integers heights where heights[i] represents the height of a bar. The width of each bar is 1.

Return the area of the largest rectangle that can be formed among the bars.

Examples

• 1 ≤ heights.length ≤ 1000
• 0 ≤ heights[i] ≤ 1000

Prerequisites

• Monotonic Stack — a stack maintaining elements in increasing or decreasing order to efficiently answer next-smaller-element queries
• Next Smaller Element Pattern — finding the nearest smaller bar on the left and right for each position sets the exact width of a rectangle
• Divide and Conquer — the minimum bar in any range limits the tallest uniform rectangle spanning that range

1. Brute Force

Intuition

Every valid rectangle is bounded by some bar as its shortest bar. For each bar i, we treat it as the height of a rectangle and find how far left and right we can extend before hitting a shorter bar. The width between those two boundary indices gives the widest rectangle where heights[i] is the limiting height.

We scan every bar and for each one expand outward in both directions. This is correct but slow — each bar may scan the entire array, giving O(n²).

Algorithm

• For each index i: expand right while heights[rightMost] ≥ heights[i], expand left while heights[leftMost] ≥ heights[i].
• Compute area = heights[i] × (rightMost − leftMost + 1).
• Track the maximum area seen and return it.

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

        for i in range(n):
            height = heights[i]

            rightMost = i + 1
            while rightMost < n and heights[rightMost] >= height:
                rightMost += 1

            leftMost = i
            while leftMost >= 0 and heights[leftMost] >= height:
                leftMost -= 1

            rightMost -= 1
            leftMost  += 1
            maxArea = max(maxArea, height * (rightMost - leftMost + 1))
        return maxArea

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

Time Complexity: O(n²)
Space Complexity: O(1)

2. Divide and Conquer (Segment Tree)

Intuition

In any range [L, R], the bar with the minimum height is the bottleneck for any rectangle spanning the full range. That gives us three cases:

• The largest rectangle uses the minimum bar and spans the entire range: area = heights[minIdx] × (R − L + 1).
• The largest rectangle lies entirely to the left of minIdx: solve recursively on [L, minIdx−1].
• The largest rectangle lies entirely to the right of minIdx: solve recursively on [minIdx+1, R].

To find the minimum bar index in any range in O(log n), we use a segment tree. This keeps the overall complexity at O(n log n).

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

        # Sparse table for range-min-index queries in O(1)
        LOG = n.bit_length()
        table = [list(range(n))]
        for k in range(1, LOG + 1):
            prev = table[k - 1]
            cur  = []
            for i in range(n - (1 << k) + 1):
                j = i + (1 << (k - 1))
                cur.append(i if heights[i] <= heights[prev[j]] else prev[j])
            table.append(cur)

        def query(l, r):
            k = (r - l + 1).bit_length() - 1
            a, b = table[k][l], table[k][r - (1 << k) + 1]
            return a if heights[a] <= heights[b] else b

        def solve(l, r):
            if l > r: return 0
            if l == r: return heights[l]
            m = query(l, r)
            return max(heights[m] * (r - l + 1),
                       solve(l, m - 1),
                       solve(m + 1, r))

        return solve(0, n - 1)

Time Complexity: O(n log n)
Space Complexity: O(n log n) for the sparse table

3. Stack — Two Pass (Left + Right Boundaries)

Intuition

For each bar to be the height of its largest possible rectangle, we need to know exactly where it can extend: the nearest shorter bar to its left and the nearest shorter bar to its right. These two boundaries define the exact width of the rectangle.

A monotonic stack efficiently answers both “next smaller element” queries. We run the stack left-to-right to fill a leftMost array, then right-to-left to fill rightMost. Finally we compute each bar's area and take the max.

Algorithm

• Left pass — for each i: pop while heights[stack[-1]] ≥ heights[i]. If stack non-empty, leftMost[i] = stack[-1] (exclusive left boundary), else -1. Push i.
• Right pass — same logic right-to-left. rightMost[i] = stack[-1] or n.
• Area pass — area = heights[i] × (rightMost[i] − leftMost[i] − 1). Adjust boundaries by ±1 to get inclusive indices first.

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

        leftMost = [-1] * n
        for i in range(n):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                leftMost[i] = stack[-1]
            stack.append(i)

        stack = []
        rightMost = [n] * n
        for i in range(n - 1, -1, -1):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                rightMost[i] = stack[-1]
            stack.append(i)

        maxArea = 0
        for i in range(n):
            width = rightMost[i] - leftMost[i] - 1
            maxArea = max(maxArea, heights[i] * width)
        return maxArea

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left  = new int[n];
        int[] right = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        int maxArea = 0;
        for (int i = 0; i < n; i++)
            maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
        return maxArea;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

4. Stack — One Pass (Start Tracking)

Intuition

We can combine the left and right boundary logic into a single left-to-right sweep. The stack stores (start_index, height)pairs in increasing height order. When a shorter bar arrives, every taller bar on the stack can't extend further right. We pop them and compute their areas.

The clever part: the popped bar's start_index becomes the start for the new shorter bar, because the new bar can extend leftward into the space the taller bar occupied (since it is shorter and therefore not blocked by whatever blocked the taller bar from the left).

Algorithm

• Initialize maxArea = 0, stack = [] storing (start, height) pairs.
• For each (i, h): set start = i.
• While stack non-empty and stack[-1][1] > h: pop (idx, ht), compute area = ht × (i − idx), update start = idx.
• Push (start, h).
• After loop, process remaining stack: each (idx, ht) extends to end, area = ht × (n − idx).

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = []  # pair: (start_index, height)

        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index
            stack.append((start, h))

        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))
        return maxArea

Time Complexity: O(n)
Space Complexity: O(n)

Common Pitfalls

Off-by-One in Width Calculation

When leftMost and rightMost are exclusive boundary indices (the first bar outside the rectangle on each side), the width formula is rightMost − leftMost − 1. Using rightMost − leftMost includes one extra bar, giving an inflated area. Always be explicit about whether your boundaries are inclusive or exclusive before writing the formula.

Forgetting to Process the Remaining Stack

After the main loop, any indices still on the stack represent bars that never encountered a shorter bar to their right — meaning they can extend all the way to the end of the histogram. Skipping the cleanup step (or the virtual sentinel bar) means missing these potentially large rectangles, especially in monotonically increasing inputs where every bar is a candidate.

# Wrong: no cleanup — bars never popped are ignored
for i, h in enumerate(heights):
    while stack and stack[-1][1] > h:
        index, height = stack.pop()
        maxArea = max(maxArea, height * (i - index))
    stack.append((i, h))
# return maxArea  ← misses remaining stack

# Correct: also process remaining bars
for i, h in stack:
    maxArea = max(maxArea, h * (n - i))

Using Strict Greater-Than When Popping

When the stack stores indices and you compare heights[stack[-1]] > heights[i] (strict), bars of equal height are not popped. This leaves multiple equal-height bars on the stack, each computing a narrower width than it should. Using ≥ ensures that when we encounter an equal-or-shorter bar, we correctly consolidate the left boundary.

Incorrect Width When Stack is Empty After Pop

If the stack becomes empty after popping an element, it means the popped bar's rectangle can extend all the way back to index 0. The width is i (not i − stack[-1] − 1, which would crash or give a wrong result). Always check if not stack before using stack[-1] as the left boundary.