Problem: Given an array of bar-heights in a histogram, find the rectangle with largest area.
Solution:
Assuming, all elements in the array are positive non-zero elements, a quick solution is to look for the minimum
element hmin in the array.
Then numElements * hmin can be one of the possible candidates for the largest area rectangle.
If that is not the largest rectangle, then the solution for the largest rectangle will not contain hmin bar.
Problem with the above algo is finding hmin which is O(n)
This converts the entire algorithm into O(n2) in the worst case.
An O(n) solution can be found as follows:
For any bar in the histogram, bounds of the largest rectangle enclosing it are
those bars which are smaller than the current bar.
This means that the largest rectangle enclosing any bar will have bars greater
than or equal to that bar.
Hence whenever we see two consecutive bars such that lk < lk-1, we know
that the rectangle for lk-1 must end there itself.
So any lk < lk-1 property tells us the right bound for rectangle of lk-1.
Exploiting this property, following algorithm can be used:
Loop over the input array and maintain a stack of increasing bar lengths.
This can be called an Increasing Stack
If current element is greater than stack-top, push it to stack top.
If current element is smaller than stack-top, then start removing elements from stack till
it has elements greater than the current.
For each popped element, find largest histogram area using:
Right boundary as current element or current element - 1 (as explained above)
Left boundary as next stack-top element or 0 (Because our stack stores only increasing
length of bars, it implies that all bars absent between two consecutive bars in the stack
must be longer than both of them)
If all elements of the stack have been popped, this means that all bars before the current
bar were longer and so their rectangles ended here. To begin afresh for the others, current
bar is put into the stack.
If any elements are left in stack after the above loop, then pop them one by one and repeat #3
Following is the code for the above:
int largestRectangle (int barHeights[], int numBars)
{
if (numBars <= 0)
return 0;
int maxArea = 0;
Stack stk = new Stack ();
stk.push (0);
for (int i=1; i < numBars; i++)
{
int currEle = barHeights[i];
while (stk.empty() == false)
{
int stackTop = stk.peep(); // peep gets stack top without removing
if ( currEle > barHeights[stackTop] )
{
stk.push (i);
break;
}
stackTop = stk.pop(); // pop gets stack top with removal
// Since stack only stores elements in increasing order, any element
// just below an element must give the leftmost boundary of the rectangle
// containing current element
// if stack is empty, then the popped element is minimum so far
int leftBoundary = stk.empty() ? 0 : stk.peep();
int rightBoundary = (barHeights[stackTop] == currEle) ? i : i-1;
int area = (rightBoundary - leftBoundary) * barHeights[stackTop];
if (area > maxArea)
maxArea = area;
}
if (stk.empty())
stk.push (i);
}
// empty the remaining stack
int rightBoundary = numBars;
while (stk.empty() == false)
{
int stackTop = stk.pop();
int leftBoundary = stk.empty() ? 0 : stk.peep();
int area = (rightBoundary - leftBoundary) * barHeights[stackTop];
if (area > maxArea)
maxArea = area;
}
return maxArea;
}
Sample execution:
Consider barHeights = [10, 40, 30, 70, 10, 30, 60]
As per the above algorithm, 'stk' and 'maxArea' will vary as follows:
1) Consider 10
stk = [0]
maxArea = 0
2) Consider 40
stk = [0, 1]
maxArea = 0
3) Consider 30
Pop elements from the stack till a minimum one is found.
So, 40 is popped. Its right-boundary is 1 and left boundary is 0, so max-area is 40
stk = [0, 2]
maxArea = 40
4) Consider 70
stk = [0, 2, 3]
maxArea = 40
5) Consider 10
Elements are popped from the stack in the inner loop.
stk = [0, 2]
rightBoundary for 70 = 3
leftBoundary for 70 = 2
maxArea = max (40,70) = 70
stk = [0]
rightBoundary for 30 = 3
leftBoundary for 30 = 0
maxArea = max(70, 90) = 90
stk = []
rightBoundary for 10 = 4
leftBoundary for 10 = 0
maxArea = max(90, 40) = 90
stk = [4]
6) Consider 30
stk = [4,5]
maxArea = 90
7) Consider 60
stk = [4,5, 6]
maxArea = 90
8) Now, elements are popped from the stack one by one.
Right boundary for all of them is 6
stk = [4,5]
maxArea = max (90, 60) = 90
stk = [4]
maxArea = max (90, 30) = 90
stk = []
maxArea = max (90, 80) = 90
Got a thought to share or found a bug in the code? We'd love to hear from you:
