Next Greater Element II || Stack Approach || Complete and Easy Explanation 🔥🔥
NOTE: First try to solve Next Greater Element I\n\n# Intuition\nIn this problem, the goal is to find the next greater element for each number in a circular arra
***NOTE:*** First try to solve [Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/)\n\n# Intuition\nIn this problem, the goal is to find the next greater element for each number in a circular array. Since the array is circular, we need to consider the array elements in a "wrapped around" manner, meaning if we don\'t find a next greater element before reaching the end of the array, we should continue searching from the beginning. We can approach this problem using a stack to efficiently keep track of potential "next greater elements" while iterating through the array.\n\n# Approach\n**Reverse the array:** \n- We reverse the input array nums to traverse it from the end to the start. This allows us to keep track of the next greater elements as we iterate, without the need to circle back explicitly.\n\n**Use two stacks:**\n- The first stack st helps track the numbers we\'ve processed so far while looking for the next greater element.\nThe second stack `st1` holds the elements of the reversed array, and helps in finding the next greater element in the circular manner.\n\n**Traverse the array:**\n- For each element, we check both stacks:\n- If the stack st contains elements smaller than or equal to the current element, we pop those elements, as they can\'t be the next greater for the current element.\n- If `st` becomes empty, we then check st1 (which acts as our circular extension of the array). If `st1` has a greater element, we use that as the answer; otherwise, we `return -1`.\n\n**Push elements to stacks:**\n- After determining the next greater element, push the current element to stack st, which will be used for the next iteration.\n\n**Reverse the result:**\n- Since we processed the reversed array, the final result `ans` must be reversed to match the original input order.\n\n# Complexity\n**Time complexity:**\nWe traverse the array twice: once to build the second stack st1 and once to calculate the next greater elements. For each element, we may push or pop from the stacks at most once. This results in an overall time complexity of $$O(n)$$, where n is the size of the array\n\n**Space complexity:**\nWe use two stacks `(st and st1)` and a result vector ans, each of which may store up to n elements. Thus, the space complexity is $$O(n)$$.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> nextGreaterElements(vector<int>& nums) {\n      \n      stack<int> st;\n      stack<int> st1;\n      st1.push(-1);\n      \n      vector<int> ans;\n      reverse(nums.begin(), nums.end());\n      int n=nums.size();\n      for(int i=0; i<n; i++){\n      st1.push(nums[i]);\n      }\n       \n      for(int i=0; i<n; i++){\n        if(st.empty()){\n            while(!st1.empty() && st1.top()<=nums[i]){\n                st1.pop();\n            }\n            if(st1.empty()) ans.push_back(-1);\n            else\n            ans.push_back(st1.top());\n            \n            st.push(nums[i]);\n        }\n        else{\n          while(!st.empty() && st.top()<=nums[i]){\n                st.pop();\n            } \n            if(st.empty()){\n              while(!st1.empty() && st1.top()<=nums[i]){\n                st1.pop();\n               }\n               if(st1.empty()) ans.push_back(-1);\n               else\n               ans.push_back(st1.top());\n               \n            } \n            else{\n                ans.push_back(st.top());\n                cout<<ans[i];  \n              }\n              st.push(nums[i]);\n        }\n      }\n      reverse(ans.begin(),ans.end());\n      return ans;\n\n    }\n};\n```
['Array', 'Stack', 'C++']