Largest Rectangle In Histogram

Problem Description

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

Examples

Constraints

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

Monotonic Increasing Stack of Boundaries

For any bar heights[i], the largest rectangle using it as the shortest bar extends left and right until it meets a bar shorter than itself. We can find these boundaries for all bars in O(n) time using a monotonic increasing stack. The stack stores pairs of (index, height). We iterate through the histogram:

• While the stack is not empty and the current height is smaller than the height at the top of the stack, we pop the top element.
• The popped bar’s height is h. The width of the rectangle is current_index - popped_index if the stack is empty, or current_index - stack_peek_index - 1 if it is not.
• We compute area = h * width and update our maximum.
• The write index for the current bar shifts back to the popped element’s start index since the current shorter bar can extend backward over the popped elements’ ranges.
• Finally, push the current bar onto the stack.

Solution 1: Monotonic Increasing Stack

Process bar indices in increasing height order and pop to calculate area bounds.

import java.util.Stack;

class Solution {
    private static class Bar {
        int index;
        int height;
        Bar(int index, int height) {
            this.index = index;
            this.height = height;
        }
    }

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        Stack<Bar> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            int start = i;
            while (!stack.isEmpty() && stack.peek().height > heights[i]) {
                Bar popped = stack.pop();
                maxArea = Math.max(maxArea, popped.height * (i - popped.index));
                start = popped.index; // current bar can extend back to the popped bar's start index
            }
            stack.push(new Bar(start, heights[i]));
        }

        // Process remaining elements in stack
        while (!stack.isEmpty()) {
            Bar popped = stack.pop();
            maxArea = Math.max(maxArea, popped.height * (n - popped.index));
        }

        return maxArea;
    }
}

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        max_area = 0
        stack = []  # stores pairs of (index, height)
        
        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                idx, height = stack.pop()
                max_area = max(max_area, height * (i - idx))
                start = idx  # current bar can extend back
            stack.append((start, h))
            
        # Process remaining elements
        for idx, height in stack:
            max_area = max(max_area, height * (len(heights) - idx))
            
        return max_area

#include <vector>
#include <stack>
#include <algorithm>

class Solution {
public:
    int largestRectangleArea(std::vector<int>& heights) {
        int n = heights.size();
        int maxArea = 0;
        std::stack<std::pair<int, int>> stack; // stores {index, height}

        for (int i = 0; i < n; i++) {
            int start = i;
            while (!stack.empty() && stack.top().second > heights[i]) {
                auto popped = stack.top();
                stack.pop();
                maxArea = std::max(maxArea, popped.second * (i - popped.first));
                start = popped.first;
            }
            stack.push({start, heights[i]});
        }

        while (!stack.empty()) {
            auto popped = stack.top();
            stack.pop();
            maxArea = std::max(maxArea, popped.second * (n - popped.first));
        }

        return maxArea;
    }
};

Complexity Analysis

• Time Complexity: O(n) because each bar is pushed to and popped from the stack at most once.
• Space Complexity: O(n) auxiliary space to store elements in the stack.

Where It Breaks

This solution requires loading the entire array in memory. If we process streaming data representing a continuous histogram, a segment tree is needed to support windowed range queries.

Common Mistakes

• Incorrect width calculation: Calculating width as i - idx - 1 without adjusting the starting index in the stack, which drops valid space from previously popped taller bars.
• Failing to clear the stack: Forgetting to process remaining elements in the stack after the loop ends, which misses rectangles that extend all the way to the right end of the histogram.

Frequently Asked Questions

Why does the starting index of the current element shift back? Because the elements popped from the stack are taller than the current element, the current element can extend all the way back to the start index of the first popped element.

What happens if the heights are strictly increasing? No elements are popped during the main loop. The final pass pops them one by one, checking areas starting from their respective indices to the end of the histogram.

← All Problems