Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example, Given height = [2,1,5,6,2,3], return 10.

https://leetcode.com/problems/largest-rectangle-in-histogram/

Solution I: Divide and conquer O(NlgN)

http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/

A simple solution is to one by one consider all bars as starting points and calculate area of all rectangles starting with every bar. Finally return maximum of all possible areas. Time complexity of this solution would be O(n^2).

We can use Divide and Conquer to solve this in O(nLogn) time. The idea is to find the minimum value in the given array. Once we have index of the minimum value, the max area is maximum of following three values. a) Maximum area in left side of minimum value (Not including the min value) b) Maximum area in right side of minimum value (Not including the min value) c) Number of bars multiplied by minimum value. The areas in left and right of minimum value bar can be calculated recursively. If we use linear search to find the minimum value, then the worst case time complexity of this algorithm becomes O(n^2). In worst case, we always have (n-1) elements in one side and 0 elements in other side and if the finding minimum takes O(n) time, we get the recurrence similar to worst case of Quick Sort. How to find the minimum efficiently? Range Minimum Query using Segment Tree can be used for this. We build segment tree of the given histogram heights. Once the segment tree is built, all range minimum queries take O(Logn) time. So over all complexity of the algorithm becomes.

Overall Time = Time to build Segment Tree + Time to recursively find maximum area

Time to build segment tree is O(n). Let the time to recursively find max area be T(n). It can be written as following. T(n) = O(Logn) + T(n-1) The solution of above recurrence is O(nLogn). So overall time is O(n) + O(nLogn) which is O(nLogn).

Solution II: Use stack

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }    

        int res = 0;

        Stack<Integer> stack = new Stack();
        int i = 0;
        while (i < height.length) {
            if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
                stack.push(i);
                i++;
            }
            else {
                int index = stack.pop();
                int len = stack.isEmpty() ? i : i - stack.peek() - 1;
                res = Math.max(res, height[index]*len);
            }
        }
        // need to pop out all elements in the stack
        while (!stack.isEmpty()) {
            int index = stack.pop();
            int len = stack.isEmpty() ? i : i - stack.peek() - 1;
            res = Math.max(res, height[index]*len);
        }

        return res;
    }
}