LeetCode Q84: 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.

Solution 1: O(N^2)

	class Solution {
	public:
	int largestRectangleArea(vector<int>& heights) {
	int largest=0;
	int preArea=0;
	for(int i=0; i<heights.size(); ++i){
	int min=INT_MAX;
	for(int j=i; j<heights.size(); ++j){
	if(i==j){
	min=heights[i];
	preArea=heights[i];
	largest=preArea>largest? preArea:largest;
	continue;
	}
	if(heights[j]<min){
	preArea=heights[j]*(j-i+1);
	min=heights[j];
	}else{
	preArea=preArea*(j-i+1)/(j-i);
	}
	largest=preArea>largest? preArea:largest;
	}
	}
	return largest;
	}
	};

view raw Q84-1.cpp hosted with ❤ by GitHub

Solution 2: Divide and Conque
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 include min value)
b) Maximum area in right side of minimum value (not include min value)
c) Number of bars multiplied by minimum value.

	class Solution {
	public:
	int helper(vector<int>&h, int left, int right){
	if(left==right)
	return h[left];
	int minv=h[left];
	int minIdx=left;
	for(int i=left; i<=right; ++i)
	if(h[i]<minv){
	minv=h[i];
	minIdx=i;
	}
	int v0=helper(h, left, max(left, minIdx-1)); // left part
	int v1=helper(h, min(right, minIdx+1), right); // right part
	int v2=minv*(right-left+1);
	return max(v0, max(v1, v2));
	}
	int largestRectangleArea(vector<int>& heights) {
	if(heights.empty())
	return 0;
	return helper(heights, 0, heights.size()-1);
	}
	};

view raw Q84-2.cpp hosted with ❤ by GitHub

Solution 3: Using stack

For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively.

We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. Following is the complete algorithm.

	class Solution {
	public:
	int largestRectangleArea(vector<int>& h) {
	stack<int> s;
	h.push_back(0);
	int p=0;
	int largest=0;
	while(!(s.empty()&&p==h.size()-1)){
	if(s.empty()&&p!=h.size()-1){
	s.push(p);
	p++;
	continue;
	}
	while(h[s.top()]<h[p]){
	s.push(p);
	p++;
	}
	int curTop=s.top();
	s.pop();
	int area;
	if(s.empty())
	area=p*h[curTop];
	else
	area=(p-s.top()-1)*h[curTop];
	largest=area>largest? area: largest;
	}
	return largest;
	}
	};

view raw Q84-3.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int largestRectangleArea(vector<int>& heights) {
	if(heights.empty())
	return 0;
	int area=0;
	stack<int> myStack;
	myStack.push(0);
	for(int i=1; i<heights.size(); i++){
	int top = heights[myStack.top()];
	if(heights[i]>=top)
	myStack.push(i);
	else{
	while(top>heights[i]&&!myStack.empty()){
	myStack.pop();
	if(!myStack.empty())
	area = max(area, (i-myStack.top()-1)*top);
	else
	area = max(area, (i)*top);
	if(!myStack.empty())
	top = heights[myStack.top()];
	}
	myStack.push(i);
	}
	}
	if(!myStack.empty()){
	int d = myStack.top();
	while(!myStack.empty()){
	int top = heights[myStack.top()];
	myStack.pop();
	if(!myStack.empty())
	area = max(area, (d-myStack.top())*top);
	else
	area = max(area, (d+1)*top);
	}
	}
	return area;
	}
	};

view raw Q84.cpp hosted with ❤ by GitHub