Friday, April 3, 2015

Largest rectangle in a histogram

The below code finds the rectangle with maximum area in a histogram with O(n) time complexity.

    public static void maxRectArea(int a[], int b[]) {
        // this is a maximization problem
        // irrespective of the height of the the next bar
        // we have to compare the area if including next bar exceeds the current area then we have to include the bar.
        // stop the expansion and proceed further until end of input.
        // 6 2 5 4 5  1 6
        // 6 2 5 8 12 1 6
        int i = 0;
        int max = -1;
        int e = 0;

        while (i < a.length) {
            if (i == 0)
                e = b[i] = a[i];
            else {
                if (a[i] < a[i-1]) {
                    int t = b[i-1] / e;
                    if (((t+1) * a[i]) < b[i-1])
                        e = b[i] = a[i];
                    else {
                        e = a[i];
                        b[i] = (t+1) * a[i];    
                    }
                }
                else if (a[i] == a[i-1]) {
                    b[i] = b[i-1] + e;
                }
                else if (a[i] > a[i-1]) {
                    if ((b[i-1] + e) > a[i]) {
                        b[i] = b[i-1] + e;
                    }
                    else {
                        e = b[i] = a[i];
                    }
                }         
            }
            i++;
        }
    }