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 heights = [2,1,5,6,2,3], return 10.

Subscribe to see which companies asked this questi

Idea:

From: http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

• (1) Create an empty stack.

• (2) Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1.

  • (a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
  • (b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).

• (3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

  Solution:

  public class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] h = heights;
        Stack<Integer> stack = new Stack();
        int ans = 0, i = 0,zero =0; 
        for(i = 0;i < h.length;){
            if(stack.isEmpty() || h[stack.peek()] <= h[i]){
                stack.push(i++);
            }
            else{
                int temp = stack.pop();
                ans = Math.max(ans, h[temp]*(stack.isEmpty()? i: i - stack.peek() -1));
            }
        }
  
        while(!stack.isEmpty()){
            int temp = stack.pop();
            ans = Math.max(ans, h[temp] * (stack.isEmpty()? i: i - stack.peek() -1));
        }
  
        return ans;
    }
  }