Friday, July 5, 2013

Largest area in a Histogram

Find the maximum area of a rectangle that fits entirely in the Histogram.

For e.g in the below histogram the maximum area of the rectangle is 2 * 80  = 160


The length of each bar will be the input, and the width of each bar is same, 1
Approach:
The naive approach can be to select one histogram at a time, find the maximum area which can be formed with this, finally return the maximum value over all the histogram.
Time Complexity O(n^2), Space Complexity O(1)
Can we do better. Lets have a look if we are computing some of the results over and over or if any of the computations are unnecessary.



Some of the key observations are:
The area of the neighbouring groups is equal to (min height of the bar in group * width of the group)
This means that we need to calculate the area formed by each minimum bar encountered so far, calculating the max of all such areas will give us the desired result.

So if we have the bars in the order given as 
9, 4, 10, 12, 16, 14, 8, 5, 1

So we need to calculate the area at the points, 4, 14, 8, 5, 1
for the ith bar which has the height h
max area = (h)*(number of contiguous bar to the left and right which has height <= h)
and the max of this is 8*5 = 40 (which is the max area of the rectangle completely inside the histogram)

So what is the data structure we can employ, 

Stack seems to be an obvious choice since we are always concerned with the element just pushed(which is the top of the stack)
Below is the piece of code which calculates the max area
int maxArea(int a[], int n ) {
    stack<int> s;
    int max = 0;
    for(int i = 0; i < n;i++) {
        while(!s.empty() && (a[i] <= a[s.top()])) {
            int h = s.top();
            s.pop();
            int l = s.empty() ? 0 : s.top() + 1;
            int m = (i - l) * a[h];
            if(m > max) max = m;
        }
        s.push(i);
    }
    while(!s.empty()) {
        int h = s.top();
        s.pop();
        int l = s.empty() ? 0 : s.top() + 1;
        int m = (n - l) * a[h];
        if(m > max) max = m;
    }
    return max;
}

Since every bar is inserted and removed only once, time complexity O(n).

1 comment :

  1. Woww, incredible solution. I've tried calculating for each i, the previous element that is less than him and store it in another array. I think that works just the same as your solution but yours is much easier to analyse and to prove it's O(n). :)

    ReplyDelete