Largest Rectangle in Histogram
For each bar, find how far left and right it can extend without hitting a shorter bar. A monotonic increasing stack efficiently finds these boundaries. When a shorter bar arrives, the popped bar's width is determined.
How It Works
Every maximal rectangle in a histogram is limited by some bar's height, extending left and right until a strictly shorter bar appears. An increasing monotonic stack finds both boundaries in one sweep: push bar indices while heights rise, and when a shorter bar arrives, pop. The popped bar's right boundary is the current index, its left boundary is the new stack top, and its area is height times that width. A sentinel bar of height 0 appended at the end flushes everything remaining.
The brute force checks every pair of boundaries in O(n²). Because each bar is pushed and popped exactly once, the stack version computes the maximum rectangle in O(n) time and O(n) space.
Step-by-Step Visualization
Code
static int largestRectangle(int[] heights) {
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
int[] h = Arrays.copyOf(heights, heights.length + 1); // Sentinel
for (int i = 0; i < h.length; i++) {
while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
int height = h[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}Tips & Gotchas
Practice Problems
- 1Largest Rectangle in Histogram
- 2Maximal Rectangle
- 3Maximum Score of a Good Subarray
About the Monotonic Stack Pattern
Keep the stack in sorted order (always increasing or always decreasing). When a new element would break the order, pop elements until the order is restored. Each popped element just found its 'answer' (the element that caused the pop).
Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).
Common Stack Interview Problems
- Valid Parentheses
- Next Greater Element
- Largest Rectangle in Histogram
- Trapping Rain Water
- Daily Temperatures
- Decode String
Frequently Asked Questions
What does popping a bar actually mean in this algorithm?
A pop happens the moment you discover the first shorter bar to the popped bar's right. Combined with the element below it on the stack (the first shorter bar to its left), you now know the exact widest rectangle that bar can support, so its area can be finalized.
How does this extend to Maximal Rectangle on a binary matrix?
Treat each row as the floor of a histogram where a cell's height is the count of consecutive 1s above it, including itself. Run the histogram algorithm once per row, giving O(rows × cols) overall.
Why append a zero-height bar at the end?
Without it, bars still on the stack after the scan never get popped and their areas are never computed. A trailing height of 0 is shorter than everything, forcing a full flush without special-case code.