Easy to understand Backtracking and Stack Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nEasy method to do the question.\n# Approach\n Describe your approach to solving the pro
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nEasy method to do the question.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nPrevious and Next Arrays: The previous and nexts functions are used to create two arrays, prev and next, which store the indices of the previous and next smaller elements for each element in the input array heights.\n\nCalculating Rectangle Area: For each element in heights, the code calculates the width of the rectangle that can be formed with that element as the height. The width is determined by the difference between the indices stored in prev and next arrays (minus one to exclude the current element).\n\nFinding Maximum Area: The code then calculates the area of each rectangle (height * width) and stores it in the ans array. Finally, it returns the maximum element from the ans array, which represents the largest rectangle that can be formed in the histogram.\n\nStack : The key idea behind this approach is to use a stack to keep track of increasing elements. When we encounter a smaller element, we pop elements from the stack until we find an element smaller than the current one. This helps us determine the previous and next smaller elements efficiently.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights)\n    {\n        int n = heights.size();\n        vector<int> prev; // Stores the index of the previous smaller element for each element\n        vector<int> next; // Stores the index of the next smaller element for each element\n        previous(prev, heights.data(), n); // Calculate the previous array\n        nexts(next, heights.data(), n); // Calculate the next array\n        vector<int> ans; // Stores the area of each rectangle\n        reverse(next.begin(), next.end()); // Reverse the next array for easier calculation\n        for(int i = 0; i < n; i++)\n        {\n            ans.push_back(heights[i] * (next[i] - prev[i] - 1)); // Calculate area for each element\n        }\n        return *max_element(ans.begin(), ans.end()); // Return the maximum area\n    }\n\n    // Function to calculate the previous array\n    void previous(vector<int>& prev, int *arr, int n)\n    {\n        stack<int> st;\n        for(int i = 0; i < n; i++)\n        {\n            while(!st.empty() && arr[st.top()] >= arr[i])\n            {\n                st.pop(); // Remove elements greater than or equal to arr[i] from stack\n            }\n            if(st.empty())\n            {\n                prev.push_back(-1); // If stack is empty, there is no previous smaller element\n            }\n            else\n            {\n                prev.push_back(st.top()); // Otherwise, store the index of the previous smaller element\n            }\n            st.push(i); // Push current element index onto stack\n        }\n    }\n\n    // Function to calculate the next array\n    void nexts(vector<int>& next, int *arr, int n)\n    {\n        stack<int> st;\n        for(int i = n-1; i >= 0; i--)\n        {\n            while(!st.empty() && arr[st.top()]>=arr[i])\n            {\n                st.pop(); // Remove elements greater than or equal to arr[i] from stack\n            }\n            if(st.empty())\n            {\n                next.push_back(n); // If stack is empty, there is no next smaller element, so n is used\n            }\n            else\n            {\n                next.push_back(st.top()); // Otherwise, store the index of the next smaller element\n            }\n            st.push(i); // Push current element index onto stack\n        }\n    }\n};\n\n```\nHope you all guys the best!!!!!
['Backtracking', 'Stack', 'Recursion', 'C++']