Largest Rectangle in Histogram

How it works

We want, for every bar, to know how wide it can stretch while still being the shortest bar in that rectangle.

A monotonic stack helps with this:

• We keep a stack of indices where the bar heights are in increasing order.
• As long as the next bar is taller or equal, we keep pushing indices.
• When we see a shorter bar, it means the bar on top of the stack can’t extend further to the right:
  • We pop it and treat it as the height of a rectangle.
  • Its width goes from the new top of the stack + 1 up to the current index − 1.

To make sure every bar eventually gets popped and processed, we run the loop one extra step with a “virtual” bar of height 0 at the end.
Each bar is pushed and popped at most once, so this is both optimal and clean.

Steps

1. Initialize:
   • maxArea = 0
   • An empty stack to store indices of bars (with heights in increasing order).
2. Loop i from 0 to n (inclusive):
   • While the stack is not empty and either:
     • i == n (we're past the last bar, acting like height 0), or
     • heights[i] is less than or equal to the height at the top index of the stack:
       • Pop the top index; let its height be h.
       • Compute the width:
         • If the stack is empty, width = i (it extends from 0 to i - 1).
         • Otherwise, width = i - stack.top() - 1.
       • Update maxArea with h * width.
   • Push the current index i onto the stack.
3. After the loop, maxArea holds the largest rectangle area. Return it.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Off-by-One Errors in Width Calculation

When computing the width of a rectangle, it is easy to miscalculate the boundaries. The width should be right - left - 1 when left and right are the indices of the nearest smaller bars (exclusive boundaries). Forgetting to subtract 1 or using inclusive boundaries incorrectly leads to wrong area calculations.

Forgetting to Process Remaining Stack Elements

After iterating through all bars, the stack may still contain indices of bars that never encountered a shorter bar to their right. These bars can extend all the way to the end of the histogram. Failing to pop and process these remaining elements misses potentially valid rectangles.

Using Strict vs Non-Strict Inequality

When comparing heights to decide whether to pop from the stack, using > versus >= matters. Using strict greater-than may cause bars of equal height to remain on the stack incorrectly, leading to wrong boundary calculations. The choice depends on how you handle the left boundary for bars with equal heights.

Incorrect Handling of Empty Stack

When the stack becomes empty while computing the left boundary, it means no shorter bar exists to the left. The width should extend from index 0 to the current position. Using stack[-1] or stack.top() on an empty stack causes runtime errors or incorrect results if not handled explicitly.

Not Handling Single-Element Arrays

Edge cases like arrays with a single bar or all bars having the same height require careful handling. The algorithm should correctly return the height of the single bar or the product of height and array length for uniform arrays without special-case bugs.

from typing import List

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

        for i in range(n + 1):
            while stack and (i == n  or heights[stack[-1]] >= heights[i]):
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                maxArea = max(maxArea, height * width)
            stack.append(i)
        return maxArea

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

        for (int i = 0; i <= n; i++) {
            while (!stack.empty() &&
                 (i == n || heights[stack.top()] >= heights[i])) {
                int height = heights[stack.top()];
                stack.pop();
                int width = stack.empty() ? i : i - stack.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
};