Maximum Area of Histogram using Stack in C++

In this article, we will provide you the code of the Maximum Area of Histogram using stack in C++. This is the most famous problem asked in the Coding Rounds of many companies like Google, Microsoft, etc.

In Data Structures and Algorithms (DSA), a stack is an abstract data type that represents a collection of elements, where elements are added and removed in a last-in-first-out (LIFO) order.

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

We earn a commission if you make a purchase, at no additional cost to you.

Steps to Solve the Problem

  1. Create two vectors v1 and v2 to store the indexes of the nearest smaller elements to the left and right of each element in the input array arr[].
    • For this, we can use the Next Smaller Element (NSE) concept with a stack. The NSE of an element in the array is the first element to its left (or right) that is smaller than the current element.
    • We can use a stack to keep track of the previous elements that are smaller than the current element. We iterate over the input array from left to right to find the NSE to the left of each element and store its index in v1.
    • Similarly, we iterate over the array from right to left to find the NSE to the right of each element and store its index in v2.
  2. Traverse the input array arr[] and for each element, calculate the area of the rectangle with that element as the minimum height.
    • The width of the rectangle is the difference between the indexes of the nearest smaller elements to its left and right, minus 1.
    • The height of the rectangle is the value of the current element.
    • Calculate the area of the rectangle with the current element as the minimum height and update the max_area variable with the maximum area found so far.
  3. Return the max_area.

Implementation of the Steps

#include <bits/stdc++.h>

using namespace std;

// NSL
vector<int> printNSL(int arr[], int n)
{
    int pseudoindex = -1;
    stack<pair<int, int> > s;  
    vector<int> v_left;
    for (int i=0;i<n;i++){
        if(s.size()==0){
            v_left.push_back(pseudoindex);
        }
        else if (s.size()>0 && s.top().first<arr[i]){
            v_left.push_back(s.top().second);
        }
        else if(s.size()>0 && s.top().first>=arr[i]){
            while(s.size()>0 && s.top().first>=arr[i]){
                s.pop();
            }
            if(s.size()==0){
                v_left.push_back(pseudoindex);
            }
            else {
                v_left.push_back(s.top().second);
            }
        }
        s.push({arr[i], i});
    }
 
    return v_left; 
}

// NSR
vector<int> printNSR(int arr[], int n)
{
    int pseudoindex = n;
    stack<pair<int, int> > s;  
    vector<int> v_right;
    for (int i=n-1;i>=0;i--){
        if(s.size()==0){
            v_right.push_back(pseudoindex);
        }
        else if (s.size()>0 && s.top().first<arr[i]){
            v_right.push_back(s.top().second);
        }
        else if(s.size()>0 && s.top().first>=arr[i]){
            while(s.size()>0 && s.top().first>=arr[i]){
                s.pop();
            }
            if(s.size()==0){
                v_right.push_back(pseudoindex);
            }
            else {
                v_right.push_back(s.top().second);
            }
        }
        s.push({arr[i], i});
    }
    reverse(v_right.begin(), v_right.end());
    return v_right;
}

int getMaxArea(int arr[], int n)
{
    vector<int> v1, v2;
    v1 = printNSL(arr, n);
    v2 = printNSR(arr, n);
    
    int max_area = INT_MIN;
    for(int i=0;i<n;i++){
        int width = v2[i] - v1[i] - 1;
        int height = arr[i];
        max_area = max(max_area, (width * height));
        
    }
    return max_area;
}

int main()
{
    int arr[] = {6,2,5,4,5,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_area = getMaxArea(arr, n);
    cout << "Maximum area of histogram: " << max_area << endl;
    return 0;
}
// contributed by Iresh Singla

The time complexity of this algorithm is O(n), where n is the size of the input array arr[]. This is because we iterate over the array only once to find the nearest smaller elements, and then again to calculate the maximum area. The space complexity is also O(n).

Leave a Reply