Largest Rectangle in Histogram
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.
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 <= 105
- 0 <= heights[i] <= 104
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest way to solve this problem is by considering each bar as the smallest (shortest) bar in the rectangle and expanding outwards. For each bar, we try to find the maximum possible rectangle by expanding to the left and right until we can no longer keep the height of that rectangle as the current bar.
Code:
- Time Complexity: O(n^2) due to nested for loops
- Space Complexity: O(1) since no extra space is used apart from few variables.
2. Better Brute Force with Pruning
Intuition:
This builds on the idea of the simple brute force but introduces a pruning step by stopping earlier when the heights decrease and thus cannot extend the rectangle further in a beneficial way.
Code:
- Time Complexity: O(n^2) due to nested for loops
- Space Complexity: O(1) since no extra space is used apart from few variables.
3. Using Stack (Optimal)
Intuition:
The most optimal solution involves using a stack to store indices of the histogram's bars. By utilizing a stack, we can ensure that we always process these histogram bars in an order where we have the necessary information to calculate the maximum rectangle as we proceed. When a lower height is encountered, we process and calculate areas for all bars taller than the current one by treating them as the smallest bar of their respective rectangles.
Code:
- Time Complexity: O(n) since iterating through the array once
- Space Complexity: O(n) due to stack.