Watch 10 video solutions for Largest Rectangle in Histogram, a hard level problem involving Array, Stack, Monotonic Stack. This walkthrough by Jackson Gabbard has 310,605 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4] Output: 4
Constraints:
1 <= heights.length <= 1050 <= heights[i] <= 104Problem Overview: You receive an array where each value represents the height of a bar in a histogram. The task is to compute the largest rectangular area that can be formed using consecutive bars. Each bar has width 1, so the challenge is identifying how far each bar can extend left and right while remaining the minimum height.
Approach 1: Monotonic Stack (O(n) time, O(n) space)
This approach uses a monotonic increasing stack to track bar indices while scanning the histogram from left to right. When the current bar height becomes smaller than the height at the stack top, the stack is popped and the popped bar is treated as the limiting height of a rectangle. The width is determined by the current index and the new stack top, giving the maximum span where that height is the minimum. Each index is pushed and popped at most once, which keeps the time complexity at O(n) with O(n) extra space for the stack.
The key insight: every bar acts as the smallest bar in some maximal rectangle. The stack helps identify the first smaller bar on both sides efficiently. This method is the industry-standard solution and appears frequently in problems involving stack, array, and monotonic stack patterns.
Approach 2: Divide and Conquer (Average O(n log n), Worst O(n^2), Space O(log n))
This strategy mirrors the logic used in maximum subarray style recursion. For any range of the histogram, find the index of the minimum height bar. The largest rectangle must be one of three possibilities: entirely in the left subarray, entirely in the right subarray, or spanning the entire range using the minimum height. Recursively compute the maximum area for the left and right segments and compare them with the area formed by the minimum bar.
The recursive depth averages O(log n) if the histogram is balanced, resulting in O(n log n) time. In the worst case (sorted heights), the recursion degenerates to O(n^2). Space usage comes from the recursion stack. This method is conceptually clean and demonstrates how global constraints can be split recursively, though it is slower than the stack-based approach.
Recommended for interviews: Interviewers expect the Monotonic Stack solution. It runs in linear time and shows strong understanding of stack-based boundary detection. Starting with the divide-and-conquer idea can show reasoning about the problem structure, but implementing the O(n) stack approach demonstrates mastery of histogram and range-boundary patterns commonly tested in technical interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Monotonic Stack | O(n) | O(n) | Best general solution. Linear scan with stack efficiently finds previous and next smaller bars. |
| Divide and Conquer | O(n log n) average, O(n^2) worst | O(log n) | Useful for understanding the recursive structure of the problem or when exploring segment-based reasoning. |