Largest Rectangle in Histogram | Leetcode 84

Welcome to one of the most infamous and challenging Stack array problems on LeetCode: Largest Rectangle in Histogram (Leetcode 84). Understanding this question is a rite of passage for cracking difficult array/stack technical interviews.

Problem Statement

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example: heights = [2, 1, 5, 6, 2, 3] => Output: 10 (The largest rectangle is formed by the bars of height 5 and 6. The rectangle has height=5 and width=2 (from index 2 to 3). Max area = 10).

Approach 1: Brute Force Evaluation O(N^2)

For every single bar at index i, we can ask the fundamental question: "If heights[i] is the absolute minimum height of my rectangle, how far left and right can I stretch it?"

If we start at a bar, we can linearly scan to the left until we hit a bar shorter than us, and linearly scan to the right until we hit a bar shorter than us. The distance between those two boundaries gives us the width!

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        max_area = 0
        n = len(heights)
        
        for i in range(n):
            min_height = heights[i]
            
            # Scan left
            left_bound = i
            while left_bound > 0 and heights[left_bound - 1] >= min_height:
                left_bound -= 1
                
            # Scan right
            right_bound = i
            while right_bound < n - 1 and heights[right_bound + 1] >= min_height:
                right_bound += 1
                
            # Calculate width and area
            width = right_bound - left_bound + 1
            max_area = max(max_area, width * min_height)
            
        return max_area

Complexity Analysis

Approach 2: Left/Right Array Precomputation O(N)

We can heavily optimize the brute force scan. Instead of scanning left and right for every single element natively, we can precompute the exact Left and Right boundaries for every single index and store them in two O(N) arrays!

We create a left_smaller array where left_smaller[i] stores the nearest index to the left that is strictly smaller than heights[i]. We can populate this using a DP-like jump optimization, heavily reducing redundant lookups.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        if n == 0: return 0
        
        left_smaller = [-1] * n
        right_smaller = [n] * n
        
        # Build Left Array
        for i in range(1, n):
            p = i - 1
            while p >= 0 and heights[p] >= heights[i]:
                p = left_smaller[p]  # Jump optimization!
            left_smaller[i] = p
            
        # Build Right Array
        for i in range(n - 2, -1, -1):
            p = i + 1
            while p < n and heights[p] >= heights[i]:
                p = right_smaller[p] # Jump optimization!
            right_smaller[i] = p
            
        max_area = 0
        for i in range(n):
            width = right_smaller[i] - left_smaller[i] - 1
            max_area = max(max_area, heights[i] * width)
            
        return max_area

Complexity Analysis

Approach 3: Monotonic Stack (One Pass Optimal)

We can compress the entire logic of Approach 2 into a single pass using a Monotonic Stack architecture.

A stack will store the indices of the bars in strictly increasing height. If we encounter a bar that is shorter than the bar at the top of the stack, it acts as the right-bound for all the tall bars piled up in the stack! We pop them off one by one, immediately calculate their isolated area (since we now know both their left bound and right bound), and continue.

graph TD
    A["Bar Sequence: [2, 1, 5, 6, 2, 3]"]
    
    B["Stack Growth (Index)"]
    C["Stack: [0] (val 2)"]
    D["Hit: 1. Pop '2'. Area=2x1. Stack: [1] (val 1)"]
    E["Stack: [1, 2] (vals 1, 5)"]
    F["Stack: [1, 2, 3] (vals 1, 5, 6)"]
    G["Hit: 2. Pop '6' Area=6. Pop '5' Area=10"]
    
    A --> B
    B --> C
    C --> D
    D --> E
    E --> F
    F --> G
    
    style G fill:#4CAF50,stroke:#fff,stroke-width:2px,color:#fff

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        max_area = 0
        stack = [] # Stack of (index, height)
        
        for i, h in enumerate(heights):
            start = i
            # While the current bar is shorter than the top of our stack
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                # Calculate the exact area this popped bar was able to span
                max_area = max(max_area, height * (i - index))
                # Push the starting point backward!
                start = index
            stack.append((start, h))
            
        # Clean up any rectangles that made it completely through to the end
        for i, h in stack:
            max_area = max(max_area, h * (len(heights) - i))
            
        return max_area

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (84)