Largest Rectangle in Histogram - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

The problem involves finding the largest rectangle area in a histogram, where each bar has a height given by the array heights. Each bar has a width of 1, and the rectangle's area is determined by the minimum height across a contiguous range of bars multiplied by the width of that range.

The solution uses a monotonic stack to efficiently compute the maximum rectangle area by tracking bars in increasing height order. Here’s how it works:

Stack Initialization: We maintain a stack of tuples (height, index), where height is the bar’s height, and index is the starting index where this height is valid. The stack is initially empty, and we track the maximum area found (max_area).
Processing Bars: For each bar at index i with height height, we set start = i as the potential left boundary. While the stack is not empty and the current height is less than the height of the top stack element (stk[-1][0]), we pop the top element (h, j):
- Compute the area of the rectangle with height h and width i - j (from index j to i-1).
- Update max_area if this area is larger.
- Set start = j, extending the current bar’s potential left boundary to the popped bar’s start index, as the current height can form a rectangle back to j.
Push Current Bar: After processing, push (height, start) onto the stack, indicating that this height is valid from index start.
Handle Remaining Bars: After the loop, pop each remaining stack element (h, j), computing the area with height h and width n - j (from j to the end of the array). Update max_area if necessary.
Result: Return max_area as the largest rectangle area found.
Why This Works: The monotonic stack ensures that heights are processed in increasing order, allowing us to compute rectangle areas when a smaller height is encountered (limiting the height of previous taller bars). The stack tracks the left boundary of each height, enabling accurate width calculations. Processing remaining bars handles cases where rectangles extend to the array’s end.
Time and Space Complexity: Each bar is pushed and popped at most once, resulting in a time complexity of O(n), where n is the number of bars. The stack stores at most n elements, so the space complexity is O(n).

Code Solution

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

        for i, height in enumerate(heights):
            start = i
            while stk and height < stk[-1][0]:
                h, j = stk.pop()
                w = i - j
                a = h*w
                max_area = max(max_area, a)
                start = j
            stk.append((height, start))
        
        while stk:
            h, j = stk.pop()
            w = n - j
            max_area = max(max_area, h*w)
        
        return max_area
        # Time: O(n)
        # Space: O(n)

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

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

        for (int i = 0; i < n; i++) {
            int height = heights[i];
            int start = i;
            while (!stk.empty() && height < stk.top().first) {
                auto [h, j] = stk.top(); stk.pop();
                int w = i - j;
                maxArea = std::max(maxArea, h * w);
                start = j;
            }
            stk.push({height, start});
        }

        while (!stk.empty()) {
            auto [h, j] = stk.top(); stk.pop();
            int w = n - j;
            maxArea = std::max(maxArea, h * w);
        }

        return maxArea;
    }
};

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

        for (int i = 0; i < n; i++) {
            int height = heights[i];
            int start = i;
            while (!stk.isEmpty() && height < stk.peek()[0]) {
                int[] popped = stk.pop();
                int h = popped[0];
                int j = popped[1];
                int w = i - j;
                maxArea = Math.max(maxArea, h * w);
                start = j;
            }
            stk.push(new int[]{height, start});
        }

        while (!stk.isEmpty()) {
            int[] popped = stk.pop();
            int h = popped[0];
            int j = popped[1];
            int w = n - j;
            maxArea = Math.max(maxArea, h * w);
        }

        return maxArea;
    }
}

var largestRectangleArea = function(heights) {
    var n = heights.length;
    var stk = [];
    var maxArea = 0;

    for (var i = 0; i < n; i++) {
        var height = heights[i];
        var start = i;
        while (stk.length > 0 && height < stk[stk.length - 1][0]) {
            var [h, j] = stk.pop();
            var w = i - j;
            var a = h * w;
            maxArea = Math.max(maxArea, a);
            start = j;
        }
        stk.push([height, start]);
    }

    while (stk.length > 0) {
        var [h, j] = stk.pop();
        var w = n - j;
        maxArea = Math.max(maxArea, h * w);
    }

    return maxArea;
};

Detailed Explanation

Understanding the Problem

The "Largest Rectangle in Histogram" problem challenges us to find the area of the largest rectangle that can be formed within a histogram. The histogram is represented as an array of integers, where each element indicates the height of a bar and all bars have equal width of 1 unit. A rectangle can span one or more adjacent bars, and its height is limited by the shortest bar within that span.

Key Insight: Using a Monotonic Stack

A brute-force approach would involve checking every possible pair of start and end indices, calculating the minimum height within the range, and then computing the area. However, this would be inefficient. Instead, we use a monotonic increasing stack to keep track of the heights and their corresponding indices. This structure allows us to compute the largest rectangle in O(n) time by systematically managing and collapsing ranges of bars.

Step-by-Step Strategy

Initialization:
Start with an empty stack and a variable max_area to store the largest area encountered.
Iterate Through Histogram:
For each index i and corresponding height in the array:
- If the current height is greater than or equal to the top of the stack, push it with its index onto the stack.
- If the current height is less, it means previous taller bars can't extend past this point. Pop from the stack and calculate the area using the popped height and the width derived from the current index and the index stored in the stack.
- After popping, push the current height and its new valid start index (from the popped element) back onto the stack.
Post-Processing Remaining Stack:
After finishing the iteration, we may have some bars left in the stack. These bars extend all the way to the end of the array. Pop each and calculate the area using the formula height × (n - index).

Why the Stack Approach Works

The stack-based method works efficiently because each bar is pushed and popped at most once. The stack maintains an increasing sequence of bar heights. When a smaller height is encountered, it acts as a boundary, triggering the calculation of maximal areas for all taller bars on the stack that can no longer extend beyond the current index.

By recording the earliest index where each height is valid, we ensure that widths are correctly computed even as we collapse prior rectangles.

Example Walkthrough

Consider the input [2, 1, 5, 6, 2, 3]. The algorithm builds the stack while maintaining increasing height order. When it reaches a height smaller than the stack top, it pops heights, calculates areas, and updates the max area. It ultimately finds that the rectangle covering [5,6] with height 5 yields the largest area of 10.

Time and Space Complexity

Time Complexity: O(n). Each bar is pushed and popped from the stack at most once.

Space Complexity: O(n). The stack may store up to n elements in the worst case.

Conclusion

This problem is a classic demonstration of how a monotonic stack can be used to optimize problems involving ranges and boundaries. The algorithm is efficient and elegant, balancing complexity and performance in a way that is both optimal and easy to reason about once understood.

Get Personalized Support at AlgoMap Bootcamp 💡