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