Pseudo-code:

text
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.

Core Insight for Largest Rectangle in Histogram

The inefficiency of the brute force method comes from repeatedly scanning the array to find how far a bar can extend. We need a way to determine the left and right boundaries for every bar in a single pass.

The core insight is that a bar at index i with height h can extend to the right until it encounters an index j where heights[j] < h. Similarly, it extends to the left until it hits an index k where heights[k] < h.

We can maintain a Monotonic Increasing Stack of indices. This stack maintains the invariant that the heights corresponding to the indices in the stack are always in strictly increasing order.

1. Push Condition: If the current bar is taller than the bar at the stack's top, we push the current index. This indicates the current bar's left boundary might be the stack top.
2. Pop Condition: If the current bar is shorter than the bar at the stack's top, we have found the Right Boundary for the bar at the stack top. The current index i is the first index to the right that is smaller.
3. Left Boundary: When we pop an index (let's call it popped_index) to process its area, the new top of the stack (after the pop) represents the first index to the left that is smaller. This is the Left Boundary.

By processing the area of a bar only when it is popped from the stack, we ensure that we know both its left limit (the element currently below it in the stack) and its right limit (the current element i that caused the pop).

Visual Description: Imagine iterating through the histogram. As long as bars are getting taller, we stack them up. The moment we see a drop in height (a smaller bar), we stop and look at the stack. The tall bars currently on the stack cannot extend past this new smaller bar. We pop the tallest bar. Its area is determined by its own height and the distance between the current "smaller" bar and the next bar remaining on the stack. We repeat this until the stack satisfies the increasing condition again.

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.

Reference Implementation

C++ Solution for LeetCode 84

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

using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        int maxArea = 0;
        int n = heights.size();
        
        for (int i = 0; i <= n; i++) {
            // Use current height or 0 if we reached the end to flush stack
            int currentHeight = (i == n) ? 0 : heights[i];
            
            // Maintain monotonic increasing stack
            while (!s.empty() && currentHeight < heights[s.top()]) {
                int h = heights[s.top()];
                s.pop();
                
                // Determine width
                // Right boundary is i
                // Left boundary is s.top() (exclusive)
                // If stack is empty, width extends from 0 to i
                int w = s.empty() ? i : i - s.top() - 1;
                
                maxArea = max(maxArea, h * w);
            }
            s.push(i);
        }
        
        return maxArea;
    }
};

Java Solution for LeetCode 84

java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
        int n = heights.length;
        
        // Iterate through all bars plus one extra iteration (i=n) to clear stack
        for (int i = 0; i <= n; i++) {
            int currentHeight = (i == n) ? 0 : heights[i];
            
            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
                int h = heights[stack.pop()];
                
                // Calculate width
                // Right boundary is i
                // Left boundary is stack.peek() (exclusive)
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                
                maxArea = Math.max(maxArea, h * w);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

Python Solution for LeetCode 84

python
class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = [] # Stores indices
        max_area = 0
        n = len(heights)
        
        # Iterate through array. 
        # We go up to n to handle the cleanup of remaining items in stack.
        for i in range(n + 1):
            # Use 0 height for index n to force pops
            current_height = heights[i] if i < n else 0
            
            while stack and current_height < heights[stack[-1]]:
                h = heights[stack.pop()]
                
                # Determine width
                # If stack is empty, width is the entire distance to i
                # Else, width is distance between current i and new top
                w = i if not stack else i - stack[-1] - 1
                
                max_area = max(max_area, h * w)
            
            stack.append(i)
            
        return max_area

Common Mistake 1: Incorrect Width Calculation

• Mistake: Calculating width as i - stack.top().
• Why: This ignores the fact that the popped element might have extended further left than the immediate neighbor if there were other elements popped before it.
• Consequence: The width is under-calculated, leading to an incorrect (smaller) area. The correct width is i - stack.top() - 1 (exclusive boundaries).

Common Mistake 2: Forgetting the "Empty Stack" Case

• Mistake: Assuming stack.top() always exists when calculating width.
• Why: When the stack becomes empty after a pop, it means the popped bar was the smallest seen so far; it extends all the way to index 0.
• Consequence: Runtime errors (accessing empty stack) or incorrect logic. If the stack is empty, width is simply i.

Common Mistake 3: Ignoring Remaining Elements

• Mistake: Returning maxArea immediately after the for loop without processing items left in the stack.
• Why: The loop only processes bars when a smaller bar is encountered. If the array is sorted increasing (e.g., [1, 2, 3]), nothing is ever popped inside the loop.
• Consequence: The function returns 0 or an incomplete max area. You must simulate a height of 0 at index n to flush the stack.