find area of largest histogram using stack

largestRectangleInHistogram.cpp

/*Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, 
find the area of largest rectangle in the histogram.

Largest Rectangle in Histogram: Example 1

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

Largest Rectangle in Histogram: Example 2

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.
*/

// C++ program to find maximum rectangular area in 
// linear time 
#include<bits/stdc++.h>
using namespace std; 

// The main function to find the maximum rectangular 
// area under given histogram with n bars 
//time complexity = O(n)
//space complexity = o(n)
int largestRectangleArea(vector<int> &A) {
    stack<int> st ;
   
    //vector left to maintain indices of nearest smaller element on left side of each i
    vector<int> left(A.size(),0);
    //vector right to maintain indices of nearest smaller element on right side of each i
    vector<int> right(A.size(),0);
   
    //using stack to find nearest smaller element on left of each i
    //if no nearest smaller element present assign -1 for that particular i 
    //O(n) operation
    for(int i = 0 ; i< A.size();i++)
    {
        while(!st.empty() && A[st.top()] >= A[i])
        {
            st.pop() ;
        }
        if(st.empty())
            left[i] = -1 ;
        else
            left[i] = st.top() ;
        
        st.push(i) ;
    }
    
    //empty the stack 
    while(!st.empty())
        st.pop() ;
    
    //using stack to find nearest smaller element on right of each i
    //if no nearest smaller element present assign A.size() for that particular i
    //O(n) operation
    for(int i = A.size() - 1 ; i >= 0 ;i-- )
    {
        while(!st.empty() && A[st.top()] >= A[i])
        {
            st.pop() ;
        }
        if(st.empty())
            right[i] = A.size() ;
        else
            right[i] = st.top() ;
        
        st.push(i) ;
    }
    
    //calculating the max Area of rectangle considering height as length of each bar
    //O(n) operation
    long long int maxArea = 0 ;
    for(int i = 0 ; i< A.size();i++)
    {
        //height is taken as length of particular bar
        int height = A[i] ;
        int width = right[i] - left[i] - 1 ;
        
        //change max area only if we find a bigger area than present maxArea
        maxArea = max(maxArea , 1LL*height*width);
    }
    return maxArea ;
} 

// Driver program to test above function 
int main() 
{ 
	vector<int> hist = {6, 2, 5, 4, 5, 1, 6}; 
	cout << "Maximum area is " << largestRectangleArea(hist); 
	return 0; 
}