# Largest Rectangle In Histogram

#### Finding the largest rectangle in histogram. Largest Rectangle in Histogram 1 : 4 * 4 = 16 units.
Largest Rectangle in Histogram 2 : 2 * 6 = 12 units.

The idea behind this algorithm is:
1. For each bar do the following

a) If the height of the current bar is greater than the height of the previous bar,
- Store the current bar’s height and the position in their respective stacks.
Else if the height of the current bar is less than the height of the previous bar
- Find the area of the largest rectangle that can be formed using the heights and the positions stored in the stack.
- Pop-out the height and the position of each bar from the stack while calculating the area of the rectangle.
- Continue finding the area using the heights stored in the stack that are greater than the current bar’s height.
- Push the height of the current bar into the height stack and the position of the previously removed bar.

2. While the height stack is not empty
- Find the area of the rectangle that can be formed using the histogram size, heights and the positions stored in the stack.
- Pop-out the height and the position of each bar from the stack while calculating the area of the rectangle.
- If the calculated area is greater than the earlier calculated areas, the largest rectangle is the newly found rectangle.

Data structure used : Stack(s). One stack is used for storing the height and the other is used for storing the indices of the bars.
Time Complexity : O(n), where n is the number of bars in histograms.

C++14 Finding the largest rectangle in the historgram.

``````#include<iostream>
#include<stack>
#include<vector>

using namespace std;
typedef vector<int> VI;
typedef stack<int> SI;

int GetArea(vector<int> histogram){

int sz = histogram.size();
stack<int> stack_of_height, stack_of_position;
int area=0;
int index=0,height=1;

for(int pos=0; pos<sz; pos++){
// If the height of the current bar is greater than the height
// at the top of stack push it.
if( stack_of_height.empty() || stack_of_height.top() < histogram[pos] ){
stack_of_height.push(histogram[pos]);
stack_of_position.push(pos);
} else {
if( stack_of_height.top() > histogram[pos] ){
// If the height of the current bar is less than the height at the top of
// the stack, pop out all the bigger heights and their corresponding positions
// and find the maximum area.
while( !stack_of_height.empty() && stack_of_height.top() > histogram[pos] ){
index  = stack_of_position.top();
stack_of_position.pop();
height = stack_of_height.top();
stack_of_height.pop();
area = max(area, height * (pos-index));
}
// Note: We are pushing height of the current bar and the position of the last removed
// index.
stack_of_height.push(histogram[pos]);
stack_of_position.push(index);
}
}
}

while(!stack_of_height.empty()){
int tempArea = stack_of_height.top() * (histogram.size() - stack_of_position.top());
stack_of_height.pop();
stack_of_position.pop();
if(tempArea > area){
area = tempArea;
}
}

return area;
}

int main(){

vector<int> vec1 = {6, 2, 5, 4, 5, 1, 6}; // 12
cout << "Histogram {6, 2, 5, 4, 5, 1, 6} : " << GetArea(vec1) << endl;
vector<int> vec2 = {6}; // 6
cout << "Histogram {6} : " << GetArea(vec2) << endl;
vector<int> vec3 = {7, 2, 1, 4, 5, 1, 3, 3}; // 8
cout << "Histogram {7, 2, 1, 4, 5, 1, 3, 3} : " << GetArea(vec3) << endl;
vector<int> vec4 = {4, 1000, 1000, 1000, 1000}; // 4000
cout << "Histogram {4, 1000, 1000, 1000, 1000} : " << GetArea(vec4) << endl;
vector<int> vec5 = { 1000, 1000, 1000, 1000}; // 4000
cout << "Histogram { 1000, 1000, 1000, 1000} : " << GetArea(vec5) << endl;
vector<int> vec6 = {2, 3, 4, 5, 5, 4, 3, 2}; // 18
cout << "Histogram {2, 3, 4, 5, 5, 4, 3, 2} : " << GetArea(vec6) << endl;
vector<int> vec7 = {5, 5, 5, 5, 5}; // 25
cout << "Histogram {5, 5, 5, 5, 5} : " << GetArea(vec7) << endl;

return 0;
}
``````

Output

``````Histogram {6, 2, 5, 4, 5, 1, 6} : 12
Histogram {6} : 6
Histogram {7, 2, 1, 4, 5, 1, 3, 3} : 8
Histogram {4, 1000, 1000, 1000, 1000} : 4000
Histogram { 1000, 1000, 1000, 1000} : 4000
Histogram {2, 3, 4, 5, 5, 4, 3, 2} : 18
Histogram {5, 5, 5, 5, 5} : 25
``````