Largest Rectangle in Histogram.cpp

//Programmed in C++ | Author: Anshuman Pratik
class Solution {
private:
    vector<int> nextSmallerElement(vector<int> arr, int n){
        stack<int> s;
        s.push(-1);
        vector<int> ans(n);

        for(int i=n-1; i>=0; i--){
            int curr = arr[i];
            while(s.top() != -1 && arr[s.top()] >= curr){
                s.pop();
            }
            ans[i] = s.top();
            s.push(i);
        }
        return ans;
    }
    vector<int> prevSmallerElement(vector<int> arr, int n){
        stack<int> s;
        s.push(-1);
        vector<int> ans(n);

        for(int i=0; i<n; i++){
            int curr = arr[i];
            while(s.top() != -1 && arr[s.top()] >= curr){
                s.pop();
            }
            ans[i] = s.top();
            s.push(i);
        }
        return ans;
    }
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> next(n);
        next = nextSmallerElement(heights, n);

        vector<int> prev(n); //Vector named prev with Size 'n' of integer type
        prev = prevSmallerElement(heights, n);

        int LargestArea = INT_MIN;

        for(int i=0; i<n; i++){
            int l = heights[i]; //Always constant length
            
            
            if(next[i] == -1){
                next[i] = n;
            }
            int b = next[i] - prev[i] -1;
            int area = l*b;
            LargestArea = max(area,LargestArea);

        }
        return LargestArea;
    }
};

//By Brute Force method, check neighbouring histogram lengths and compute area. Alternatively, if width is equal or greater of either sides of bar then compute extended area of histogram. Width can be (next-previous-1) bar. In case of equal height throughout i.e. same values in vector, then directy substitute size to next.
//Time Complexity(T.C) and Space Complexity(S.C) = O(n)