Largest Rectangle in Histogram
Problem
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.
- 1 ≤ heights.length ≤ 10⁵
- 0 ≤ heights[i] ≤ 10⁴
Example
heights = [2,1,5,6,2,3]10A brute-force approach would check every possible rectangle by iterating over all pairs of bars and calculating the minimum height in that range, resulting in O(n^2) time complexity. Instead, the algorithm uses a stack to track bars in increasing order of height. When a bar shorter than the top of the stack is encountered, it means the rectangle with the height of the popped bar can no longer extend to the right. The algorithm calculates the area for that bar considering the current index as the right boundary and the index stored in the stack as the left boundary. This process continues until the stack is empty or the current bar is taller than the top of the stack. After processing all bars, the algorithm calculates areas for the remaining bars in the stack considering the histogram's end as the right boundary. This approach efficiently computes the largest rectangle in O(n) time by ensuring each bar is pushed and popped at most once.
Approach
Straightforward Solution
A brute-force approach checks every pair of bars and finds the minimum height in that range to calculate the area, resulting in O(n^2) time complexity, which is too slow for large inputs.
Core Observation
The largest rectangle for any bar is limited by the first smaller bar to its left and right. By maintaining a stack of bars in increasing height order, the algorithm can efficiently find these boundaries for each bar.
Path to Optimal
The key recognition signals are 'largest rectangle', 'histogram bars', and 'contiguous bars'. These indicate the Monotonic Stack pattern because the problem requires efficiently finding the nearest smaller elements to the left and right for each bar to determine maximal width. The stack maintains indices of bars in increasing order, allowing constant-time access to these boundaries when a smaller bar is encountered.
Optimal Approach
Use a monotonic increasing stack to store pairs of (start index, height). Iterate through the bars, and for each bar, pop from the stack while the current bar is shorter than the top of the stack. For each popped bar, calculate the area using its height and the width determined by the current index and the popped bar's start index. Push the current bar with the updated start index onto the stack. After processing all bars, pop remaining bars and calculate areas considering the histogram's end as the right boundary. This guarantees O(n) time complexity as each bar is pushed and popped once.
Time
O(n)
Each bar is pushed onto the stack once and popped at most once, resulting in linear time complexity.
Space
O(n)
The stack can hold up to n bars in the worst case, requiring O(n) auxiliary space.
Pattern Spotlight
Monotonic Stack (Nearest Smaller Elements for Range Queries)
Maintain a stack of bars in increasing height order so that when a shorter bar appears, it signals the end of rectangles for taller bars; popping these bars reveals their maximal width bounded by the current index and the previous smaller bar.
Solution
| 1 | class Solution:
|
| 2 | def largestRectangleArea(self, heights: list[int]) -> int:
|
| 3 | max_area = 0
|
| 4 | stack = []
|
| 5 |
|
| 6 | for i, h in enumerate(heights):
|
| 7 | start = i
|
| 8 | while stack and stack[-1][1] > h:
|
| 9 | index, height = stack.pop()
|
| 10 | max_area = max(max_area, height * (i - index))
|
| 11 | start = index
|
| 12 | stack.append((start, h))
|
| 13 |
|
| 14 | for i, h in stack:
|
| 15 | max_area = max(max_area, h * (len(heights) - i))
|
| 16 |
|
| 17 | return max_area |
| 1 | class Solution { |
| 2 | public int largestRectangleArea(int[] heights) { |
| 3 | int maxArea = 0; |
| 4 | Deque<int[]> stack = new ArrayDeque<>(); |
| 5 | |
| 6 | for (int i = 0; i < heights.length; i++) { |
| 7 | int h = heights[i]; |
| 8 | int start = i; |
| 9 | while (!stack.isEmpty() && stack.peek()[1] > h) { |
| 10 | int[] bar = stack.pop(); |
| 11 | int index = bar[0]; |
| 12 | int height = bar[1]; |
| 13 | maxArea = Math.max(maxArea, height * (i - index)); |
| 14 | start = index; |
| 15 | } |
| 16 | stack.push(new int[] {start, h}); |
| 17 | } |
| 18 | |
| 19 | while (!stack.isEmpty()) { |
| 20 | int[] bar = stack.pop(); |
| 21 | int index = bar[0]; |
| 22 | int height = bar[1]; |
| 23 | maxArea = Math.max(maxArea, height * (heights.length - index)); |
| 24 | } |
| 25 | |
| 26 | return maxArea; |
| 27 | } |
| 28 | } |
Step-by-Step Solution
Initialize Maximum Area and Monotonic Stack
| 3 | max_area = 0
|
| 4 | stack = []
|
Objective
To set up variables for tracking the maximum rectangle area and maintain a stack of bars in increasing height order.
Key Insight
Initializing max_area to zero provides a baseline for comparison. The stack stores tuples of (start index, height) to track bars and their earliest possible start positions, enabling efficient width calculation when bars are popped.
Interview Quick-Check
Core Logic
The stack maintains bars in increasing height order, storing their start indices to calculate widths when popping.
State & Boundaries
max_area starts at zero and updates only when a larger rectangle is found.
Process Each Bar and Calculate Areas by Popping Taller Bars
| 6 | for i, h in enumerate(heights):
|
| 7 | start = i
|
| 8 | while stack and stack[-1][1] > h:
|
| 9 | index, height = stack.pop()
|
| 10 | max_area = max(max_area, height * (i - index))
|
| 11 | start = index
|
| 12 | stack.append((start, h))
|
Objective
To iterate through each bar, pop taller bars from the stack when a shorter bar is encountered, and calculate the maximal rectangle areas for those popped bars.
Key Insight
When the current bar is shorter than the top of the stack, it signals that rectangles with heights of the popped bars cannot extend further right. By popping these bars and calculating areas using their heights and widths determined by the current index and their stored start indices, the algorithm efficiently finds maximal rectangles. Updating the start index to the popped bar's index ensures that the current bar can extend as far left as possible.
Interview Quick-Check
Core Logic
Popping bars taller than the current bar identifies rectangles that end at the current index, enabling area calculation with correct width.
State & Boundaries
The while loop continues until the stack is empty or the top bar is not taller than the current bar.
Common Pitfalls & Bugs
Failing to update the start index after popping leads to incorrect width calculations for the current bar.
Calculate Areas for Remaining Bars After Full Iteration
| 14 | for i, h in stack:
|
| 15 | max_area = max(max_area, h * (len(heights) - i))
|
Objective
To compute maximal rectangle areas for bars remaining in the stack after processing all histogram bars, considering the histogram's end as the right boundary.
Key Insight
Bars left in the stack have no smaller bar to their right, so their maximal rectangles extend to the end of the histogram. Calculating areas using their heights and widths from their stored start indices to the histogram's length ensures no potential maximal rectangle is missed.
Interview Quick-Check
Core Logic
Remaining bars in the stack represent heights extending to the histogram's end, so their maximal rectangles use the histogram length as the right boundary.
State & Boundaries
Iterate through all remaining bars to ensure all maximal rectangles are considered.
Return the Maximum Rectangle Area Found
| 17 | return max_area |
Objective
To return the largest rectangle area computed after processing all bars.
Key Insight
The max_area variable has been updated throughout the iteration and final processing steps to hold the largest rectangle area found, so returning it provides the correct solution.
Interview Quick-Check
Core Logic
Returning max_area yields the largest rectangle area found in the histogram.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
while stack and stack[-1][1] > h:While the stack is not empty and the top bar's height is greater than the current bar's height, pop from the stack.
Encountering a shorter bar signals the end of rectangles for taller bars; popping them allows calculation of their maximal rectangle areas bounded by the current index.
max_area = max(max_area, height * (i - index))Update max_area with the maximum of current max_area and the popped bar's area.
Calculating area as height times width (current index minus popped bar's start index) captures the largest rectangle for that bar ending at the current position.
max_area = max(max_area, h * (len(heights) - i))Update max_area with the maximum of current max_area and the area of the remaining bars extending to the histogram's end.
Calculating area as height times (histogram length minus start index) ensures all potential maximal rectangles are considered.
stack = []Initialize an empty stack to store pairs of (start index, height).
The stack maintains bars in increasing height order, enabling efficient calculation of rectangle widths when bars are popped.
start = indexUpdate the start index to the popped bar's start index.
This allows the current bar to extend leftward to the earliest position of the popped taller bar, ensuring correct width calculation when pushed onto the stack.
start = iSet the start index for the current bar to its own index initially.
This start index may be updated if taller bars are popped, allowing the current bar to extend leftward as far as possible.
index, height = stack.pop()Pop the top bar's index and height from the stack.
Removing the taller bar from the stack prepares for area calculation and updates the start index for the current bar.
stack.append((start, h))Push the current bar's start index and height onto the stack.
Adding the current bar maintains the monotonic increasing order of the stack and records the earliest start index for future area calculations.
for i, h in stack:Iterate through remaining bars in the stack after processing all histogram bars.
Remaining bars have no smaller bar to their right, so their maximal rectangles extend to the histogram's end and must be evaluated.
for i, h in enumerate(heights):Iterate through each bar's index and height in the histogram.
Processing bars sequentially allows the algorithm to maintain the monotonic stack invariant and calculate maximal rectangles as shorter bars appear.
return max_areaReturn the maximum rectangle area found.
max_area holds the largest rectangle area computed, so returning it provides the correct solution.
max_area = 0Initialize max_area to zero to track the largest rectangle found.
Starting with zero ensures any valid rectangle area found will update this value, establishing a baseline for comparison.
Test Your Understanding
Why does the algorithm pop bars from the stack when encountering a shorter bar, and how does this help compute the largest rectangle?
Because a shorter bar indicates that the rectangle with the popped bar's height cannot extend beyond the current index. Popping allows calculation of the maximal rectangle area for that height using the current index as the right boundary and the previous smaller bar's index as the left boundary.
Related Problems
Stacks pattern
Don't just read it. Drill it.
Reconstruct Largest Rectangle in Histogram from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Largest Rectangle in Histogram drill