81. Largest Rectangle in Histogram

For each bar, expand left and right to find the widest rectangle that uses this bar's height as the limiting height.

Brute Force

For each bar at index i, treat heights[i] as the rectangle's height. Expand leftward while bars are at least as tall, then expand rightward. The width is (right - left + 1). Track the maximum area across all bars.

This requires O(n) expansion per bar, giving O(n²) time overall. Space is O(1).

Why it's slow: every bar re-scans its neighbours, leading to redundant comparisons.

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

Maintain a stack of bar indices in increasing height order. When a shorter bar is found, pop taller bars and compute their rectangles — the stack tells us exactly how far left each popped bar can extend.

Mental Model

Imagine walking left to right through the histogram. Keep a stack of bar indices whose heights are in strictly increasing order. When you encounter a bar shorter than the stack's top, you know the top bar's rectangle can't extend further right — so pop it and calculate its area. The new stack top tells you how far left it extends.

Algorithm Steps

1. Initialise an empty stack and max_area = 0.
2. For each index i from 0 to n-1: a. While the stack is non-empty and heights[i] < heights[stack[-1]]:
   • Pop top = stack.pop().
   • Width = i - stack[-1] - 1 if stack is non-empty, else i.
   • Area = heights[top] * width.
   • Update max_area. b. Push i onto the stack.
3. After the loop, pop remaining bars (right boundary = n).
4. Return max_area.

Worked Walk-through

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

Result: 10

Edge Cases

• All same height: one rectangle spanning the entire array
• Sorted ascending: largest is the last pop during drain
• Single bar: area equals its height

Complexity

• Time: O(n) — each index is pushed and popped at most once.
• Space: O(n) — the stack holds at most n indices.