Largest Rectangular Area in a Histogram in C++

In this tutorial, we are going to learn how to find the Largest Rectangular Area in a Histogram with the help of C++ programming. First, we will cover the introduction of the histogram and then the problem will be explained and finally, we find the solution.

Histogram and Stack explained

A histogram is a graph that 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. Our task is to find the area under this rectangle.

There are many solutions to this problem:

1. The 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).

Before we write our code, let’s see the algorithm:

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 than the given bar then pop until the smaller bar is reached or stack is empty.
3. Remove every bar from the stack until it is 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 program, 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++