All 4 approaches shown || O(N^2) || O(NlogN) || O(N)(two pass) || O(N)(one pass) with explanation
I will try to explain all the three approaches I know for solving this problem : \n1) Brute Force  O(n^2)(too slow TLE)\nwe can compute area of every subarray a
I will try to explain all the three approaches I know for solving this problem : \n**1) Brute Force  O(n^2)**(too slow **TLE**)\nwe can compute area of every subarray and return the max of them all.\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int n = heights.size() ; \n\t\tint max_area = 0 ; \n\t\tfor(int i = 0 ; i < n ; i++) {\n\t\t\tint curr_max = 0 ; \n\t\t\tint min_height = INT_MAX ; \n\t\t\tfor(int j = i ; j < n ; j++) {\n\t\t\t\tmin_height = min(min_height , heights[j]) ; \n\t\t\t\tcurr_max = max(curr_max , min_height * (j - i + 1)) ; \n\t\t\t}\n\t\t\tmax_area = max(max_area , curr_max) ; \n\t\t}\n\t\treturn max_area ; \n    }\n};\n```\n\n**2) Divide n Conquer Approach O(NlogN)(using segment tree) O(N^2)(if we calculate range minimum naively)**\nWe can use Divide and Conquer to solve this in O(nLogn) time.\nThe idea is to find the minimum value in the given array.\nOnce we have index of the minimum value, the max area is maximum of following three values :\n1. Maximum area in left side of minimum value ( excluding the min value)\n2. Maximum area in right of minimum value ( excluding the min value)\n3. Minimum value * length of segment .\nThe areas on left and right can be calculated recursively.\nIf we use linear search to find the minimum value, then the worst case time complexity of this algorithm becomes O(n^2).**(TLE)**\n```\nclass SegmentTree {\npublic: \n    int start , end , min ; \n    SegmentTree *left ;\n    SegmentTree *right ;\n    \n    SegmentTree (int start, int end) {\n        this->start = start ;\n        this->end = end ;\n        left = right = NULL ;\n    }  \n};\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        SegmentTree* root = build(heights , 0 , heights.size() - 1) ;\n        return maxAreaInThisSegment(heights , 0 , heights.size() - 1 , root) ;\n    }\n    \n    SegmentTree* build(vector<int>& heights, int start, int end) {\n        if (start > end) return NULL ;\n        SegmentTree *root = new SegmentTree(start, end) ;\n        if (start == end) {\n            root->min = start ;\n        return root ;\n        } else {\n          int middle = (start + end) / 2 ;\n          root->left = build(heights, start, middle) ;\n          root->right = build(heights, middle + 1, end) ;\n          root->min = heights[root->left->min] < heights[root->right->min] ? root->left->min : root->right->min ;\n          return root ;\n        }\n    }\n    \n    int query(vector<int> &heights , int start , int end , SegmentTree* root) {\n        if(!root || end < root->start || start > root->end) return -1 ;\n        if (start <= root->start && end >= root->end) {\n            return root->min ;\n        }\n        int leftMin = query(heights , start , end , root->left) ;\n        int rightMin = query(heights , start , end , root->right) ; \n        if(leftMin == -1)   return rightMin ;\n        if(rightMin == -1)  return leftMin ; \n        return heights[leftMin] < heights[rightMin] ? leftMin : rightMin ; \n    }\n    //calculates the maximum possible area in the histogram between indexes start and end\n    int maxAreaInThisSegment(vector<int> &heights , int start , int end , SegmentTree *root) {\n        if(start > end) {\n            return -1 ;\n        } \n        if(start == end) {\n            return heights[start] ;\n        }\n        int wholeMin = query(heights , start , end , root) ; \n        return max({heights[wholeMin] * (end - start + 1) , maxAreaInThisSegment(heights , start , wholeMin - 1 , root) , maxAreaInThisSegment(heights , wholeMin + 1 , end , root)}) ;\n    }\n};\n```\n\n**3) Using left_smaller and right_smaller O(N)(2 pass)**\nwe use two arrays left and right which store the next smaller element to the left and right respectively.\nthen for every index we calculate area as `heights[i] * (right[i] - left[i] + 1)`\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int n = heights.size() ; \n        vector<int> left(n , 0) , right(n , n) ; \n        stack<int> s ; \n        for(int i = 0 ; i < n ; i++) {\n            while(!s.empty() && heights[i] <= heights[s.top()]) s.pop() ;\n            if(s.empty())   left[i] = 0 ; //minimum element\n            else    left[i] = s.top() + 1 ;\n            s.push(i) ; \n        }\n        while(!s.empty())   s.pop() ; \n        for(int i = n - 1 ; i >= 0 ; i--) {\n            while(!s.empty() && heights[i] <= heights[s.top()]) s.pop() ;\n            if(s.empty())   right[i] = n - 1 ; //minimum element\n            else    right[i] = s.top() - 1 ;\n            s.push(i) ; \n        }\n        int max_area = 0 ; \n        for(int i = 0 ; i < n ; i++) {\n            max_area = max(max_area , heights[i] * (right[i] - left[i] + 1)) ;\n        }\n        return max_area ;\n    }\n};\n```\n**4) using only one stack O(N)(1 pass)**\nsame as approach 3 but better space complexity **(O(N) space)**\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int n = heights.size() , max_area = INT_MIN , i = 0 ; \n        stack<int> s ;\n        while(i < n) {\n            if(s.empty() || heights[s.top()] <= heights[i]) {\n                s.push(i) ; \n                i++ ; \n            } else {\n                int prev_top = s.top() ; \n                s.pop() ; \n                max_area = max(max_area , heights[prev_top] * (s.empty() ? i : i - s.top() - 1)) ;\n            }\n        }\n        while(!s.empty()) {\n            int prev_top = s.top() ; \n            s.pop() ; \n            max_area = max(max_area , heights[prev_top] * (s.empty() ? i : i - s.top() - 1)) ;\n        }  \n        return max_area ;\n    }\n};\n```\n\n
['Divide and Conquer', 'Stack', 'Tree', 'Recursion', 'C']