Largest Rectangular Area in a Histogram in C++

In this tutorial, we are going to learn how to find Largest Rectangular Area in a Histogram in C++. Firstly an introduction of the histogram. Secondly the problem is explained and finally, we find the solution.

Histogram and Stack explained

The histogram is a graph which consists of bars. The bars show the value of each corresponding to the y-axis.

The histogram has joined different bars and all can be continues to each other and form a rectangular area. We have to find the area under this rectangle.

There are many solutions to this problem:




  1. First, one is Divide and Conquer.
  2. The second one is using a stack.

In this tutorial, we are going to use the stack method. This method is very efficient and has a time complexity of O(n).

The algorithm we are going to use is:

  1. Create an empty stack
  2. Check the top of the stack if it is smaller than the given bar then push into the stack and if the top is bigger then the given bar then pop until the smaller bar is reached or stack is empty.
  3. Remove every bar from the stack until its empty.

Program to find maximum area of histogram

#include<iostream> 
#include<stack> 
using namespace std; 
  
int areahist(int hist[], int n) 
{ 
    stack<int> s; 
  
    int max_area = 0; 
    int tp;  
    int area_with_top; 
  
    int i = 0; 
    while (i < n) 
    { 
        if (s.empty() || hist[s.top()] <= hist[i]) 
            s.push(i++); 
  
        else
        { 
            tp = s.top(); 
            s.pop();  
  
            area_with_top = hist[tp] * (s.empty() ? i :  
                                   i - s.top() - 1); 
  
            if (max_area < area_with_top) 
                max_area = area_with_top; 
        } 
    } 
  
    while (s.empty() == false) 
    { 
        tp = s.top(); 
        s.pop(); 
        area_with_top = hist[tp] * (s.empty() ? i :  
                                i - s.top() - 1); 
  
        if (max_area < area_with_top) 
            max_area = area_with_top; 
    } 
  
    return max_area; 
} 

int main() 
{
  int n;
  cout<<"Enter the number of bars in histogram : ";
  cin>>n;
  int hist[n];
  cout<<"Enter the values of Histogram : ";
  for(int i=0;i<n;i++){
    cin>>hist[i];
  }
    cout << "Maximum area is " << areahist(hist, n); 
    return 0; 
}

Input and Output:

Enter the number of bars in histogram : 5
Enter the values of Histogram : 10 20 10 30 20
Maximum area is 50

In the above code, we have taken a stack and operations as given before being executed.

Also Checkout:

Heap Sort in C++

Program to find the area of the parallelogram in C++


Leave a Reply

Your email address will not be published. Required fields are marked *