Largest Rectangle in Histogram

This article covers the intuition, workflow, dry run, C++ implementation, complexity, and interview usage for Largest Rectangle in Histogram.

1. Intuition

Each bar can act as the minimum height of a rectangle. The main question becomes: how far can that height extend left and right before a smaller bar blocks it?

2. How It Works

1. Use a monotonic increasing stack of indices
2. When a lower height arrives, pop taller bars
3. For each popped bar, compute width from the new stack top to the current index
4. Track the maximum area

3. Pattern Recognition

Think of this when you see:

• largest rectangle
• range controlled by nearest smaller elements
• skyline or histogram area

4. Dry Run Example

Input:

heights = [2, 1, 5, 6, 2, 3]

Step-by-step execution:

• 5 and 6 grow the stack
• 2 arrives, so pop 6 and then 5
• compute areas 6 * 1 and 5 * 2 = 10
• maximum remains 10

Final Output:

10

5. Code (C++)

int largestRectangleArea(vector<int>& heights) {
  stack<int> st;
  heights.push_back(0);
  int best = 0;

  for (int i = 0; i < static_cast<int>(heights.size()); i++) {
    while (!st.empty() && heights[st.top()] > heights[i]) {
      int height = heights[st.top()];
      st.pop();
      int left = st.empty() ? -1 : st.top();
      int width = i - left - 1;
      best = max(best, height * width);
    }
    st.push(i);
  }

  return best;
}

6. Complexity Analysis

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

7. When to Use

• histogram area
• maximal rectangle in matrix after row transformation

8. Common Mistakes

• forgetting the sentinel 0
• computing width incorrectly after popping

9. Variations / Extensions

• maximal rectangle in a binary matrix

10. LeetCode Practice Problems

Medium

• https://magicsheet.dev/questions/largest-rectangle-in-histogram/

Hard

• https://magicsheet.dev/questions/maximal-rectangle/

11. Key Takeaways

• Histogram problems are really nearest-smaller-boundary problems
• Width calculation depends on the stack after popping

Back: Stack, Queue, and Heap Patterns