Algorithms
Maximum area rectangle of histogram
Given n non-negative integers representing the height of bars of width one of a histogram, find the maximum area rectangle of histogram i.e. the maximum area rectangle contained in the histogram.
For example, H = [4, 2, 1, 8, 6, 8, 5, 2] then the histogram has a rectangle of area of 20 showed in shaded.
H[i] ^
| __ __
8 | | | | |
| | |__| |
6 | | | | |__
5 |__ | | | | |
4 | | | | | | |
3 | |__ | | | | |__
2 | | |__| | | | | |
1 |__|__|__|__|__|__|__|__|_______
0 1 2 3 4 5 6 7 i
H[i] ^
| __ __
8 | | | | |
7 | | |__| |
6 | | | | |__
5 |__ |xx|xx|xx|xx|
4 | | |xx|xx|xx|xx|
3 | |__ |xx|xx|xx|xx|__
2 | | |__|xx|xx|xx|xx| |
1 |__|__|__|xx|xx|xx|xx|__|_______
0 1 2 3 4 5 6 7 i
Observe that a rectangle can be constructed by combining consecutive bars such that the shortest bar is contained completely within the rectangle i.e.
The largest rectangle, including the bar i as the smallest bar in the rectangle, is the longest rectangle of width equal to the height of the bar (i.e. H[i]). The rectangle can be stretched in the left side until we hit the first smaller bar, and can be stretched in the right until the first smaller bar.
Let’s define some terms.
R[i] = Area of the largest rectangle with the bar at i is as the smallest bar in the rectangle (i.e. width = H[i])
left[i] = the left most boundary of R[i], which is the leftmost bar greater than H[i].
right[i] = the right most boundary of R[i], which is the rightmost bar greater than H[i].
R[i] = max{H[i], H[i]*(right[i]-left[i]+1)}.
Goal: Maximize R[i], i.e. Rmax=max{R[i]} 0<=i<=n-1.
For example: largest rectangle area including 5th bar (i=4) as the smallest bar is = H[4] * (right[4]-left[4]+1) = 6x(5-3+1) = 18 sq. unit. Question is how to compute left[i] and right[i] most efficiently?
Brute-force solution
The O(n^2) brute-force solution would be to compute for each bar i, the index of first smaller element on the left , smallerLeft[i] and the index of first smaller element on the right, smallerRight[i]. Then,
left[i] = smallerLeft[i]+1;
right[i] = smallerRight[i]-1;
R[i] = max{H[i], H[i]*(smallerRight[i]-smallerLeft[i]-1)}.
Goal: Maximize R[i], i.e. Rmax=max{R[i]} 0<=i<=n-1.
O(n) solution : Greedy
Observe that if the bars are all in decreasing order then left[i] = 0 as the rectangle (with the current bar i as the smallest bar) can be extended as left as possible, and right[i] = i as the rectangle (with current bar i as the smallest bar) is not extendable to the right. That is,
left[i] = 0,
right[i] = i,
R[i] = max{H[i], H[i]*(right[i]-left[i]+1)} = max{H[i], H[i]*(i+1)}, 0<=i<=n-
1.
But what if the histogram is not either strictly increasing or deceasing? That is it is a mix of increasing and decreasing sequence.
Solution
The idea is that we can partition the bars into smaller histograms such that all the bar in a partition are monotonically increasing (or monotonically decreasing). We will find maximum rectangles in the sub-histograms (greedy) and then combine the solutions to get the maximum of the whole histogram.
For example, we partition the above histogram, H into 3 decreasing order sub-histograms. We also found the left and right indices of each of the sub-histograms. Note that left/right indices contain the absolute index of the left/right of i in the current partition. For example: 0 index for partition 2 is the index 3 in the absolute original histogram.
H[i] ^
| __ __
8 | | | | |
7 | | |__| |
6 | | | | |__
5 |__ | | | | |
4 | | | | | | |
3 | |__ | | | | |__
2 | | |__| | | | | |
1 |__|__|__|__|__|__|__|__|_______
0 1 2 3 4 5 6 7 i
|---p1---|-p2--|---p3---|
H[i] = [4, 2, 1,|8, 6,| 8, 5, 2]
left[i] = [0, 0, 0,|3, 3,|5, 5, 5 ]
right[i] = [0, 1, 2,|3, 4,|5, 6, 7 ]
R[i] = [4, 4, 3,|8,12,|8,10, 6 ]
greedy max = [4 | 12,| ,10 ]
Global max = [ ? ]
So, far so good! We have divided the problem into subproblems and computed greedy solution (local best) for each of the smaller subproblems. Now, we need merge these smaller subproblem solutions to get the solution for the bigger problem! We can merge a partition to its adjacent right partitions in order to create the global maxima in a successive manner (greedy). Notice that we only create a new partition (i.e. stating a new subproblem) when current bar is greater then the smallest element of the last partition.
So, we can push a new bar into the stack when the new bar is not part of current decreasing sub-histogram. Which means it is not less than the top bar in the stack. So, when we pop an item out, the new top in the stack should be the first one in the left that is smaller than the popped one. That is,
left[i] = top.
Also, when we pop an item up, it means that we hit a new height that is smaller than it. That is,
right[i] = i.
So, for each popped bar i, R[i] = H[i]*(i-top-1).
At the end of a single pass on the histogram we computed the greedy max in a number of sub-histograms. Now, we will do a pass on the current stack to combine the sub-histogram solutions. Below is a O(n) solution to the above idea using O(n) space stack data structure. Although the inner-loop seems to execute O(n^2) but in fact the stack is only pushing a bar just once. So, time complexity is O(n).
public static int maxRectangleAreaHistogram(int hist[]){
int maxArea = 0;
Stack<Integer> stack = new Stack<Integer>();
int n = hist.length;
int i = 0;
while(i < n){
//push a new bar if -
//1. it is in current subhistogram if monotonic decreasing bars, or
//2. we found a start of a new subhistogram
if(stack.isEmpty() || stack.peek() <= hist[i]){
stack.push(i++);
}
//we found a bar in monotonic decreasing order while we already have a start bar on the stack
//so, compute area upto to the last pushed bar
else{
//pop the last pushed bar
int lastBarIndex = stack.pop();
int height = hist[lastBarIndex];
//leftmost bar in which can be either -
//1. first bar if no bar on the stack, or
//2. the top bar on the stack
int leftMaxBarIndex = stack.isEmpty() ? 0 : stack.peek();
//right index is always current index
int rightBarIndex = i;
//width between right bar and left bar
int width = rightBarIndex - leftMaxBarIndex - 1;
//compute area and update max area
maxArea = Math.max(maxArea, height*width);
}
}
while(!stack.isEmpty()){
//pop the last pushed bar
int lastBarIndex = stack.pop();
int height = hist[lastBarIndex];
//leftmost bar in which can be either -
//1. first bar if no bar on the stack, or
//2. the top bar on the stack
int leftMaxBarIndex = stack.isEmpty() ? 0 : stack.peek();
//right index is always current index
int rightBarIndex = i;
//width between right bar and left bar
int width = rightBarIndex - leftMaxBarIndex - 1;
//compute area and update max area
maxArea = Math.max(maxArea, height*width);
}
return maxArea;
}