Easy Stack Solution
\n# Approach\nApproach:\n\nThis problem can be solved easily and efficiently by using the stack data structure as it is based on the Last in First out (LIFO) pr
\n# Approach\nApproach:\n\nThis problem can be solved easily and efficiently by using the stack data structure as it is based on the Last in First out (LIFO) principle.\n\nTo make it a bit easier let\u2019s first try to solve without considering the array as circular. To find the next greater element we start traversing the given array from the right. As for the rightmost element, there is no other element at its right. Hence, we assign -1 at its index in the resultant array. Since this can be the next greater element (NGE) for some other element, we push it in the stack S. We keep checking for other elements. Let\u2019s say we are checking for an element at index i. We keep popping from the stack until the element at the top of the stack is smaller than A[i]. The main intuition behind popping them is that these elements can never be the NGE for any element present at the left of A[i] because A[i] is greater than these elements. Now, if the top element of S is greater than A[i] then this is NGE of A[i] and we will assign it to res[i], where res is the resultant array. If the stack becomes empty then it implies that no element at the right of A[i] is greater than it and we assign -1. At last, we push A[i] in S.\n\nDry run: Let\u2019s apply this algorithm for A[] = {5,7,1,2,6,0}:\n\n\n\nSo, the resultant array is {7,-1,2,6,-1,-1}. Remember that we have considered the array to be non-circular. For a circular array, the resultant array should be {7,-1,2,6,7,5}. \n\nNow we need to make this algorithm work for a circular array. The only difference between a circular and non-circular array is that while searching for the next greater element in a non-circular array we don\u2019t consider the elements left to the concerned element. This can be easily done by inserting the elements of the array A at the end of A, thus making its size double. But we actually don\u2019t require any extra space. We can just traverse the array twice. We actually run a loop 2*N times, where N is the size of the given array.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:0(2N+2N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:0(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> nextGreaterElements(vector<int>& nums) {\n    stack<int>st;\n    int n = nums.size();\n    vector<int>ans(n,-1);\n    for (int i = 2 * n - 1; i >= 0; i--)\n    {\n        while(!st.empty() && st.top() <= nums[i % n])\n        {\n            st.pop();\n        }\n        if(i<n)\n        {\n            if(!st.empty())\n            {\n                ans[i]=st.top();\n            }\n         \n        }\n                st.push(nums[i%n]);\n    }\n    return ans;\n    }\n};\n```
['Stack', 'C++']