Largest Rectangle in Histogram

LeetCode 84: Largest Rectangle in Histogram Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a monotonic increasing stack to find the nearest smaller bars on the left and right for every element in $O(N)$ time, calculating the maximum possible area where each bar acts as the height bottleneck.

The LeetCode 84 problem asks us to find the area of the largest rectangle that can be formed within a histogram. We are given an array of integers representing the heights of bars, assuming each bar has a width of 1. We must determine the contiguous sub-array of bars that forms the largest rectangular area, where the height of the rectangle is limited by the shortest bar in that sub-array.

This is a classic interview problem that tests the ability to optimize geometric array problems using stack-based data structures.

Brute Force Approach for Largest Rectangle in Histogram

The naive approach involves checking every possible pair of bars to define the start and end of a rectangle, or alternatively, expanding outwards from every bar to find its maximum width.

For each bar at index i, we can treat heights[i] as the height of a potential rectangle. We then expand to the left and right as long as the adjacent bars are greater than or equal to heights[i]. Once we hit a bar smaller than heights[i] (or the array boundaries), we stop. The width is the distance between these boundaries.

Pseudo-code:

max_area = 0
for i from 0 to n-1:
    height = heights[i]
    left = i
    right = i
    
    // Expand left
    while left >= 0 and heights[left] >= height:
        left--
        
    // Expand right
    while right < n and heights[right] >= height:
        right++
        
    width = (right - 1) - (left + 1) + 1
    max_area = max(max_area, height * width)
    
return max_area

Complexity Analysis: The time complexity is $O(N^2)$. In the worst case (e.g., a sorted array like [1, 2, 3, 4, 5]), for every bar, the inner loops traverse a significant portion of the array. Given the constraint $N \le 10^5$, an $O(N^2)$ solution performs approximately $10^{10}$ operations, which results in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Stack Patterns

1. Initialize an empty stack to store indices.
2. Initialize maxArea to 0.
3. Iterate through the heights array using an index i.
4. While the stack is not empty AND the current bar heights[i] is less than the bar at the index at the top of the stack:
   • This means the bar at stack.top() cannot extend further right.
   • Pop the top index; let this be h_index.
   • The height of the rectangle is heights[h_index].
   • The right boundary is the current index i.
   • The left boundary is the new stack.top() (if the stack is empty, the width extends to the very beginning).
   • Calculate width: i - stack.top() - 1 (or i if stack is empty).
   • Update maxArea.
5. Push the current index i onto the stack.
6. Cleanup: After the loop finishes, the stack may still contain elements. These are bars that never found a smaller bar to the right. Their right boundary is the end of the array (index n).
   • Process the remaining elements in the stack using the same logic, treating the current index as n.

Execution Flow

Let's trace heights = [2, 1, 5, 6, 2, 3].

1. i = 0, height = 2: Stack empty. Push 0. Stack: [0] (vals: [2]).
2. i = 1, height = 1: 1 < 2. Pop 0.
   • Height: heights[0] = 2.
   • Right Boundary: 1.
   • Stack empty $\to$ Left Boundary: -1.
   • Width: 1 - (-1) - 1 = 1. Area: 2 * 1 = 2. Max: 2.
   • Push 1. Stack: [1] (vals: [1]).
3. i = 2, height = 5: 5 > 1. Push 2. Stack: [1, 2] (vals: [1, 5]).
4. i = 3, height = 6: 6 > 5. Push 3. Stack: [1, 2, 3] (vals: [1, 5, 6]).
5. i = 4, height = 2: 2 < 6. Pop 3.
   • Height: heights[3] = 6.
   • Right: 4. Left: 2 (stack top).
   • Width: 4 - 2 - 1 = 1. Area: 6 * 1 = 6. Max: 6.
   • Stack: [1, 2] (vals: [1, 5]).
   • 2 < 5. Pop 2.
   • Height: heights[2] = 5.
   • Right: 4. Left: 1 (stack top).
   • Width: 4 - 1 - 1 = 2. Area: 5 * 2 = 10. Max: 10.
   • Stack: [1] (vals: [1]).
   • 2 > 1. Push 4. Stack: [1, 4] (vals: [1, 2]).
6. i = 5, height = 3: 3 > 2. Push 5. Stack: [1, 4, 5] (vals: [1, 2, 3]).
7. End of array: Process remaining stack with i = 6.
   • Pop 5 (height 3): Width 6 - 4 - 1 = 1. Area 3.
   • Pop 4 (height 2): Width 6 - 1 - 1 = 4. Area 8.
   • Pop 1 (height 1): Width 6 - (-1) - 1 = 6. Area 6.
8. Result: 10.

Proof of Correctness

The algorithm ensures correctness by systematically considering every bar as the shortest bar in a potential rectangle. For any specific bar x, the widest possible rectangle with height heights[x] extends from the first element smaller than x on the left to the first element smaller than x on the right.

The monotonic stack invariant guarantees that when we pop an index, we have correctly identified these exact boundaries. Since the maximum area rectangle must have some bar that serves as its minimum height bottleneck, and we calculate the max area for every bar serving as that bottleneck, the global maximum area is guaranteed to be found.

Pattern Reuse Notes

The logic used in LeetCode 84: Largest Rectangle in Histogram is directly applicable to:

• LeetCode 85: Maximal Rectangle: This problem involves a 2D binary matrix. By treating each row as the base of a histogram (accumulating heights from rows above), you can solve LeetCode 85 by running the LeetCode 84 algorithm on each row.

Reference Implementation

C++ Solution for LeetCode 84

1#include <vector>
2#include <stack>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9    int largestRectangleArea(vector<int>& heights) {
10        stack<int> s;
11        int maxArea = 0;
12        int n = heights.size();
13        
14        for (int i = 0; i <= n; i++) {
15            // Use current height or 0 if we reached the end to flush stack
16            int currentHeight = (i == n) ? 0 : heights[i];
17            
18            // Maintain monotonic increasing stack
19            while (!s.empty() && currentHeight < heights[s.top()]) {
20                int h = heights[s.top()];
21                s.pop();
22                
23                // Determine width
24                // Right boundary is i
25                // Left boundary is s.top() (exclusive)
26                // If stack is empty, width extends from 0 to i
27                int w = s.empty() ? i : i - s.top() - 1;
28                
29                maxArea = max(maxArea, h * w);
30            }
31            s.push(i);
32        }
33        
34        return maxArea;
35    }
36};

Java Solution for LeetCode 84

1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class Solution {
5    public int largestRectangleArea(int[] heights) {
6        Deque<Integer> stack = new ArrayDeque<>();
7        int maxArea = 0;
8        int n = heights.length;
9        
10        // Iterate through all bars plus one extra iteration (i=n) to clear stack
11        for (int i = 0; i <= n; i++) {
12            int currentHeight = (i == n) ? 0 : heights[i];
13            
14            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
15                int h = heights[stack.pop()];
16                
17                // Calculate width
18                // Right boundary is i
19                // Left boundary is stack.peek() (exclusive)
20                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
21                
22                maxArea = Math.max(maxArea, h * w);
23            }
24            stack.push(i);
25        }
26        
27        return maxArea;
28    }
29}

Python Solution for LeetCode 84

1class Solution:
2    def largestRectangleArea(self, heights: list[int]) -> int:
3        stack = [] # Stores indices
4        max_area = 0
5        n = len(heights)
6        
7        # Iterate through array. 
8        # We go up to n to handle the cleanup of remaining items in stack.
9        for i in range(n + 1):
10            # Use 0 height for index n to force pops
11            current_height = heights[i] if i < n else 0
12            
13            while stack and current_height < heights[stack[-1]]:
14                h = heights[stack.pop()]
15                
16                # Determine width
17                # If stack is empty, width is the entire distance to i
18                # Else, width is distance between current i and new top
19                w = i if not stack else i - stack[-1] - 1
20                
21                max_area = max(max_area, h * w)
22            
23            stack.append(i)
24            
25        return max_area