Algotree > Algorithms > Stack Based > Largest Rectangle In Histogram

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