LeetCode · #84

Largest Rectangle in Histogram Solution

Given an array of bar heights, find the area of the largest rectangle that can be formed within the histogram.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #84

🏗️

Pattern

Monotonic Stack — increasing order

Given an array heights where heights[i] is the height of the i-th bar (width = 1), return the area of the largest rectangle that can be formed in the histogram.

Example

 Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10 // Rectangle of height 5, width 2 (bars at index 2 and 3) → 5×2 = 10 

Constraints

• 1 ≤ heights.length ≤ 10⁵ • 0 ≤ heights[i] ≤ 10⁴

Section Two · Approach 1

Brute Force — O(n²)

For each bar, expand left and right to find the widest rectangle using that bar's height as the minimum. Area = height × width.

Problem: O(n) expansion per bar → O(n²) total. A monotonic increasing stack determines the left and right boundaries for each bar in a single pass — when a bar is popped, we know exactly how far it extends.

Java — Brute Force

 class Solution {
public int largestRectangleArea(int[] heights) {
int max = 0;
for (int i = 0; i < heights.length; i++) {
int minH = heights[i];
for (int j = i; j < heights.length; j++) {
                minH = Math.min(minH, heights[j]);
                max = Math.max(max, minH * (j - i + 1));
            }
        }
return max;
    }
}

Python — Brute Force

 class Solution:
def largestRectangleArea(self, heights: list[int]) -> int:
        max_area = 0 for i in range(len(heights)):
            min_h = heights[i]
for j in range(i, len(heights)):
                min_h = min(min_h, heights[j])
                max_area = max(max_area, min_h * (j - i + 1))
return max_area

Metric	Value
Time	O(n²)
Space	O(1)

Section Three · Approach 2

Monotonic Stack — O(n)

Maintain a stack of indices in increasing height order. When a bar is shorter than the stack's top, the taller bar can no longer extend right — pop it and compute its area. The width extends from the new stack top (left boundary) to the current index (right boundary).

💡 Mental model: Imagine building towers from left to right. Each tower stands as tall as its bar. When you encounter a shorter bar, all taller towers to the left get "capped" — they can't extend further right. At that moment, calculate each capped tower's maximum rectangle: its height × how far it spans. The stack remembers which towers are still "uncapped."

Algorithm

Step 1: Push indices onto stack while heights are non-decreasing.
Step 2: When heights[i] < heights[stack.peek()]: pop index top.
Step 3: Width = i − stack.peek() − 1 (or i if stack is empty). Area = heights[top] × width.
Step 4: After scanning all bars, pop remaining stack entries using i = n as the right boundary.

🎯 Why increasing order?:

In an increasing stack, the bar at the top is always the tallest unresolved bar.
When a shorter bar arrives, we know the tall bar's rectangle can't extend further right (it's blocked).
We also know its left boundary — the previous stack entry. This gives us both boundaries in O(1).

Section Four · Trace

Visual Walkthrough

Trace through heights = [2, 1, 5, 6, 2, 3]:

Monotonic Increasing Stack — pop and compute area

Section Five · Implementation

Code — Java & Python

Java — Monotonic Stack

 import java.util.Stack;
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
for (int i = 0; i <= heights.length; i++) {
int h = (i == heights.length) ? 0 : heights[i]; // sentinel while (!stack.isEmpty() && h < heights[stack.peek()]) {
int top = stack.pop();
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, heights[top] * width);
            }

            stack.push(i);
        }
return maxArea;
    }
}

Python — Monotonic Stack

 class Solution:
def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []
        max_area = 0 for i in range(len(heights) + 1):
            h = heights[i] if i < len(heights) else 0 # sentinel while stack and h < heights[stack[-1]]:
                top = stack.pop()
                width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, heights[top] * width)

            stack.append(i)
return max_area

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n²)	O(1)	Expand left/right per bar
Divide & Conquer	O(n log n)	O(log n)	Recursively split at min height
Monotonic Stack ← optimal	O(n)	O(n)	Each bar pushed/popped once. Sentinel simplifies cleanup.

Sentinel trick:

By appending a height-0 bar at the end (using i == n), we force all remaining bars to be popped in the final iteration.
This eliminates the need for a separate cleanup loop after the main pass.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single bar	`[5]`	Area = 5 × 1 = 5.
All same height	`[3, 3, 3]`	Area = 3 × 3 = 9. Stack stays sorted, drained at sentinel.
Ascending	`[1, 2, 3, 4]`	No pops until sentinel. Widest rectangle is min×n or tallest×1.
Descending	`[4, 3, 2, 1]`	Each bar pops the previous. Many small rectangles compared.
Contains zeros	`[2, 0, 2]`	Zero bar blocks extension. Rectangles on each side are independent.

⚠ Common Mistake: Getting the width calculation wrong when the stack is empty. If the stack is empty after popping, the popped bar's rectangle extends from index 0 to i-1 — width is i, not i - stack.peek() - 1. Always check stack.isEmpty() before peeking.

← Back to Stack problems

LearningTree

LC 84 · Largest Rectangle in Histogram — Solution & Explanation | DSA Guide