Algorithm Day74 - Largest Rectangle in Histogram

Posted on In , Views:

🧩 Problem Description

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

💬 Examples

Example 1

1
2
3
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is formed by bars with height 5 and 6, width = 2 → area = 10.

Example 2

1
2
Input: heights = [2,4]
Output: 4

💡 Intuition

We want to find the largest rectangle area in a histogram.
A monotonic increasing stack helps track the left and right boundaries for each bar:

  • Traverse the bars.
  • While current height is less than the top of stack, pop from stack and calculate area.
  • Area = poppedHeight * (currentIndex - stackTopAfterPop - 1).
  • Push current index onto the stack.
  • Add sentinel 0 at the end to flush out remaining bars.

🔢 Java Code (Monotonic Stack)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        
        for (int i = 0; i <= n; i++) {
            int h = (i == n ? 0 : heights[i]);
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

⏱ Complexity Analysis

  • Time: O(n) — each bar pushed and popped at most once.
  • Space: O(n) — stack storage.

✍️ Summary

  • Use monotonic increasing stack to efficiently compute rectangle areas.
  • Each bar defines a rectangle extended until a smaller bar appears.

Related problems

  • lc-85 — Maximal Rectangle
  • lc-42 — Trapping Rain Water
  • lc-239 — Sliding Window Maximum