Circular Next Greater Element Solution using Stack
Complete this problem before attempting [Next Greater Element]\n# Intuition\nThe problem asks us to find the next greater element for each element in the circul
Complete this problem before attempting [[Next Greater Element](https://leetcode.com/problems/next-greater-element-i/)]\n# Intuition\nThe problem asks us to find the next greater element for each element in the circular array `a`. To solve this, we can use a stack to keep track of elements in `a`. We\'ll iterate through `a` twice, effectively treating it as a circular array. For each element in `a`, we\'ll find the next greater element using the same approach as in the Next Greater Element I problem.\n\n# Approach\n1. Initialize a stack to keep track of elements in `a` and a vector `ans` to store the next greater element for each element in `a`. Initialize all elements of `ans` to -1.\n2. Iterate through `a` twice.\n   - For each element in `a`, pop elements from the stack until we find an element greater than the current element.\n   - If there\'s an element in the stack, store it as the next greater element for the current element; otherwise, store `-1`.\n   - Push the current element into the stack.\n3. Return `ans`.\n\n# Complexity\n- Time complexity: \\( O(n) \\), where \\( n \\) is the size of `a`. We iterate through `a` twice, effectively making it \\( 2n \\), but in terms of complexity analysis, we consider it \\( O(n) \\).\n- Space complexity: \\( O(n) \\), where \\( n \\) is the size of `a`. We use a stack and a vector to store elements and their next greater elements.\n\n# Code\n```cpp\nclass Solution {\npublic:\n    vector<int> nextGreaterElements(vector<int>& a) {\n        int n = a.size();\n        vector<int> ans(n, -1);\n        stack<int> st;\n        \n        // Iterate through a twice\n        for (int k = 0; k < 2; ++k) {\n            for (int i = n - 1; i >= 0; --i) {\n                while (!st.empty() && st.top() <= a[i]) {\n                    st.pop();\n                }\n                if (!st.empty()) {\n                    ans[i] = st.top();\n                }\n                st.push(a[i]);\n            }\n        }\n        return ans;\n    }\n};\n```
['Stack', 'C++']